I had my watch replaced by apple, after getting the new one , it was asking to connect to my iphone. Once it was pairing it would say ""not connected to internet"" check your wifi or internet and make sure bluetooth is enabled. i tried different things , my internet is working, wifi working and so was my bluetooth.
I then kept my phone (Xs) on airplane mode, with internet (wifi) enabled and blue tooth. The phone and watch paired , it then started to update my watch. It worked