For my iPhone 7 + Series 2, I realized that my phone <-> watch didn't appear to even have reliable communication: the widgets weren't keeping up-to-date and most actions that required inter-device communication were flaky at best. My iPhone updated to the latest beta (2 and 3) just fine, but the watch was stuck on beta 1 due to the same "not connected to the internet" problem. For me, I had to:
1) Un-pair the watch (which ultimately failed from the phone)
2) Reset/erase the watch (which appeared to fail, but upon a manual reboot was successfully wiped)
3) Re-pair the devices. I setup the watch as a new device; not sure if this was required, but my confidence was so low at this point that it seemed the most likely successful path forward.
4) Re-install the beta profile on the watch.
5) OTA update was recognized at this point, and I was able to update the watch.
Hope that helps somebody else.