This is very annoying & persistent issue with very simple solution: connect to a different WiFi network and try again.
My Watch was collecting dust for a year because of me being unable to find a solution. I tried every possible thing shown on every single site. I was ready to give up, the last thing I wanted to try was to pair it with some other iPhone. Went to my office to ask people if someone can borrow me their iPhone. While waiting for someone with an iPhone to show up I decided to give it another try since now I'm on a different network. Guess what? It freaking worked. After a freaking year of head banging, all it needed was different WiFi network. Mind you that I tried via cellular network, that one didn't work either. IDK what was causing this, was it CGNAT my provider introduced or some glitch between my Apple Watch - iPhone - Router I don't know. I'm happy it's fixed, hopefully it will work for you too.
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!