2022 update, using iPhone 12 Pro Max & Apple Watch Series 5: it's Beem335i's solution that worked for me, you really do have to sign out of your Apple iD to make this work. I'll copy-paste their response below to save you all the scroll time...
I finally fixed it, guys! This is what I did to get it to finally update...
1. Hard reset apple watch > when the apple logo shows hold down the button next to the crown and hold for 30 seconds > select erase all settings and content.
2. After watch resets > power down the watch do not hard reset, move the power slider to the right you might have to put in your wrist to do that and then put it back on the charger.
3. On your iPhone sign out of iCloud completely > go to settings > general > scroll down > shut down iphone (do not hard reset)
4. Power up Watch and then your iPhone > sign into iCloud/AppleID
5. Start the pairing process > it should say your watch is now paired > select update > it will give you the update error again saying no internet but let it sit for a minute > boom it will start updating the watch. Headache is GONE hopefully!
Hope this works for everyone because after trying everything these are the steps that I took you might have to try a few times but mine worked the very first try.
Frustrated that this is what I've had to do, but it's worked. Finally!
I solved this issue by uninstalling the Watch app from my iphone and reloading it. After reloading the app I paired the watch to the phone and the update started loading.
I will say one thing today was a frustrating day trying to get the watch to pair for a few hours. Finally I have success. My fix is the same as many but it took only one try when I changed the Country and Language. I decided to use language Portuguese, and country Afghanistan. It worked. so mad I could not see straight. But success, hope it works for you. It will.
Apple Watch 3, iPhone 11Pro w/ iOS 14.6 - nothing works to update the watch and make it a usable device, it's basically a dud now. I've tried resetting the iPhone and trying to update the watch in different language. No dice!