I've been trying to fix this watch on and off for almost two years. Even the Apple Store couldn't fix this for me. They said it was likely a hardware failure and recommended that I just but a new one. "The cost to repair will be about SGD$365 and the cost of a new SE model is around $415, so it's only $50 more to get a new one that will have a one year warranty."
But a combination of suggestions above worked for me. I hope it works for you, too.
Details of my devices:
Series 3 38mm watch
iPhone 7 plus
Steps that worked for me:
A: Make sure your phone has the latest version of iOS. This will be needed since the phone OS needs to be current to support the newest version of WatchOS which will be installed by the phone.
B: Hard reset the phone (my main phone is an iPhone 12 Pro, but I have an old iPhone 7 Plus I was able to use. I don't know if the solution is specific to devices.)
Press and hold both the volume down button and the Sleep/Wake button at the same time.
When the Apple logo appears, release both buttons.
C: Hard reset the watch
Turn off the watch completely from the side button below the digital crown.
Turn it back on, and when you see the Apple logo, press and hold the same button for 30+ seconds until it tells you you're about to wipe all contents from the Apple Watch.
D: Start the pairing process.
I've seen some say to use the manual process where you enter the code. Mine worked just by placing the two devices close to each other and following on-screen instructions.
NOTE: This entire process took HOURS to complete. My WiFi is very fast, but maybe it was the fact that the devices are older. It took about 3 hours to get through the downloading/preparing/installing phases, and then it actually stuck at the verifying stage overnight. I finally just pulled the watch from the charge and restarted it, and it was paired at that point and worked just fine!
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!