I also hit this issue trying to set up a service replacement from Apple. I spent hours trying all these suggestions on my main iPhone 11 without success. I even set up an old iPhone 8 from scratch (as a new phone, but still linked to my iCloud account) and that still failed in the same way.
The solution for me was to set the watch up using my wife’s iPhone and iCloud account first - the update went through first time. I then removed it from her account and was then able to set it up successfully on my phone and iCloud account, as it didn’t need to do the update, so didn’t hit this error.
So, for me at least, it seems to be some sort of issue with my iCloud account (or some data synced to it), possibly related to the way the Genius removed my old watch from my account when I took it in for servicing.
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!