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.