Unfortunately, none of the solutions above worked for me. My apple watch software was not up to date and my watch was wiped of all data and unpaired. I couldn't pair my phone to update it and I could not update it because it wasn't paired. The solution was to try to pair my watch to another phone to update the software. In this case it was my husband's iphone 6. I was able to get past the "not connected to internet error" and proceeded with the watch software update. Once the update was complete and after hard resetting the watch, I was able to successfully pair my watch with my new phone. FWIW - I was trying to update / pair an apple watch series 3 (don't know what the last software version was - but definitely WAY outdated) and an iPhone 12 Pro Max (software version 14.6). Hope this helps!