I ran into this issue when trying to pair my iPhone X running iOS 15.1 with my Apple Watch Series 5 trying to update to watchOS 8.1.
I was able to get to the screen which asks to update the OS on the operating system.
When I tapped the 'Update Now' button, I notice a modal flash on the screen with buttons 'Dismiss' | 'Update' that displays for less than a second and disappears without prompt. I couldn't read the message but it seemed like it was related to the update.
The iPhone screen immediately redirected to the spinning screen 'Checking for Updates' after which I get the error 'Unable to check for update - you are not connected to the internet' (Try Again | Start Over).
I tapped on 'Start Over' again to unpair and go through the process again. When I re-tried the update by tapping the 'Update now' button, I immediately tapped the area where the 'Update' button on the brief modal would display briefly and somehow I was able to see the watchOS 8.1 Software Update screen.
Hopefully this will help someone else save time as I went through pretty much all of the other suggestions (hard reset, change of region, etc) to no avail.
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!