Wanted to share my solution if people are continuing to face this problem. I had this issue just today "not connected to internet" . I tried resetting watch, uninstalling app on iphone and evrything.. Nothing worked.
Finally tried this..and it worked for me
Pressed the i on the watch before pairing. Tried a different country location (india) and the problem went away.
Different associated locations of your apple id and iwatch may cause this issue.. So lets say your apple id is setup for india and you are in the US and trying to pair your new watch, try setting the watch location to india as above.