I’ve had the watch since last May, and originally had it paired to my iPhone 11. I just upgraded to iPhone 13 and the watch only connects to the internet when my phone is connected to a wireless network. Even then, the phone reports that the watch isn’t paired.
I’ve gone to the Watch app on my phone and clicked the button that says “Pair an existing Watch,” but no joy.
Before I plan a trip to the Apple Store on my next day off, does anyone have any suggestions?
With this message and the errors you’ve gotten, I’d bet on @BigT 's point, that you haven’t unpaired and/or reset the watch from the old phone. In general, with smartwatches, you unpair, which may or may not do a factory reset on the watch anyway, and then pair with the new phone. Lots of generalities because it works differently between the various smartwatch OS and manufacturers.
Here is apple’s support docs for the process -
It includes options if you don’t have the old phone as well as if you do.
I turned in the old phone to T-Mobile and deleted everything from it. Then this morning I called tech support and a nice young man named Daniel walked me through a reset of the watch so I could pair it as a new watch (instead of an existing watch).