I own Apple Watch Series 1 and I tried all the above solutions for 2 days and nothing worked for me.
Below are the steps that worked for me, I hope it helps someone!
Please note: My problem started when I Erased all my settings and contents on the Apple watch, when I started to connect my watch to new phone then this problem arisen.
Made sure my Iphone is up to date with all the latest software updates
Sign out of the ICloud account on your Iphone
Hard refresh the Iphone --> Pressing Volume UP button once, down button once and holding the power button until the phone is turned off.
Delete the Watch app from Iphone
Hard Refresh the Iphone again
Hard refresh the Watch
Install the Watch app again
Then tried to pair the watch with the Phone worked, it started downloading new update.
Hope this helps someone! Good Luck
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!