I had the exact same problem. I tried to troubleshoot using different methods for over a month & have attempted to update the watch using 3 different wifi networks but to no avail. Today I bit the bullet and took my iPhone & Apple Watch into the Apple store. While waiting for a technician to become available, I decided to connect to Apple’s wifi & tried updating again. To my surprise, this worked. The no internet connection alert disappeared and the watch began updating on Apple’s wifi straight away. The estimated update time was 3 hours so I left my phone and watch with the technician and came back 3 hours later. My watch is now setup and working great! I hope this helps!