It seems a bug in the watch app is to blame. I ran the update on mine as my watch was effected with the bug ( series 1 on 12 pro max iOS 15 beta 3 ). The watch app is telling you your phone is out of date on every device ive tried. My iPhone 6s on 14.7 reports in the app the phone is out of date , iPhone 11 Pro Max on iOS reports out of date and iPhone 12 Pro Max does the same.
The later phones you get a very fast and can't read grey pop up square with ' YOUR PHONE IS OUT OF DATE AND REQUIRES AN UPDATE - CANCEL - UPDATE ' This is far too fast to read on later phones however on my iPhone 6 it pops up and stays up.
I got around the by borrowing an iPhone 6 on 12.x.x which was fully updated to whet is finally supported , I paired it with the 6 which then gave phone out of date message in watch app. While the 6 was doing this nonsense again like other phones I paired the watch simultaneously to the iPhone 12 and stated the update and it worked , updated , synced etc.... I then unpaired it from the 12 and the watch then paired with all devices I own.
The issue is the App reporting the phone is out of date even on phones in date for the series of watch at the same period in time ie. old iPhone 6 and series 1 should just work as both released around the same time give or take.
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!