It’s been a while since this post but I solved my issue with the watch not wanting to update and error message saying “not connected to internet.” I clicked on settings and entered my ICloud, I erased all of the watch data and deleted the app. I reinstalled it and it instantly started to work with my Apple Watch Series 3. My watch was factory reset so I couldn’t do anything on the watch, only on the iPhone. Check it out! Hope this helps!