I fixed that issue with a simple step!
I got my new watch and same thing happened.
Then I remembered I have split my WIFI bands to 2.4Ghz and 5Ghz
I checked my router setting and realised that
my phone was connected to 5Ghz and watch automatically connected to 2.4Ghz.
This caused them thinking I have no internet connection.
So I switched off 5Ghz on router and it went on with installing update straight away!