Had the same issue. I did notice that before the screen that gives the option to select update there is a screen that pops up for less than a second and disappears. I had to do a video recording on another phone so I could replay the video to see the pop-up. It’s another screen giving the option to update the watch os. Is has two options, “dismiss” or “update”. I restarted the pairing processes. Then I continuously tapped the screen where the pop-up had the “update” option. It then did the watch software update, and the pairing was successful.