I finally figured this out after two months of frustration. I have an iPhone 12 and an Apple series 4 watch. I could not get past update and not connected to the internet. Today, I decided to try pairing it with an old iPhone 7 we have around. It worked! I could update the watch! Then I reset the watch and started to pair it again with my iPhone 12. Everything went almost smoothly. It stated there was another update needed to 8.4. When I did that update, I got stuck on the ‘what wrist will you be wearing this on’. I started over again and chose to skip the update and continue. It worked like a charm. I tried every single option offered on this over the months. Seriously, every one of them. So the trick is to find an older phone with WiFi connection and it should allow you to update. Not sure why this worked, but it did!