There are a whole lot of things tried in this forum - I think this really has to do with a 2.4 GHz wifi signal. This appears to be the ONLY connection to the internet that "counts."
To resolve - I went into my router settings and switched OFF my 5 GHz signal (only leaving my 2.4 GHz signal active) - as soon as I did it started working (To force the connection to wifi I did disable my Cellular data.).
I think most other cases suggested were when people got lucky and happened to have been connected over 2.4 GHz (like leaving things connected overnight, etc.) There are certain cases where a dual band router will switch the signal you're on and sometimes you can just get lucky. I do have to admit when I was at work I did multiple hard resets, etc. but nothing worked until I purposefully connected over 2.4 GHz.
iPhone 11 - iOS 15.1
Apple watch series 3
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!