After spending couple hours trying to figure out the "Unable to Check for Update," issue on my Apple Watch series 5 setup, I found something that worked for me.
I first did what @heisenbert suggested and hard set set the phone.
Press Volume Up and let go.
Press Volume Down and let go.
Press and hold the side button.
NOTE*: This does not wipe any data from your phone"
Then, I also did a hard reset before pairing the watch to my phone and wiped all content from the watch.
You do this by:
-Turning off the watch completely from the side Botton below the digital crown.
-Turn it back on, and when you see the apple logo pop up, press and hold the same Botton for 30+ second
until it ask to wipe all content of the Apple Watch.
Once both of those steps are completed, I went and started paring the watched to my phone. Make sure you press the option do pair it manually and enter the sequence of numbers displayed on the Apple Watch. From there on, I was able to update the Apple Watch with no issues. This update took me more than an hour so keep that in mind.
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!