Whilst not directly related to an Apple watch 5, my Apple watch series 3 had this same issue of the not connected to internet error. I tried all the things mentioned in this thread and others. Here is what worked for me: On your iPhone go to settings>wifi and tap the "i" next to the wifi network you are connected to. Scroll down to DNS and change it to manual. Delete every server entry on the list. Add the servers "1.1.1.1", 1.0.0.1" "8.8.8.8" and "8.8.4.4". Then hit save. Now try and pair your apple watch - it should work, mine went ahead and downloaded the 8.0.1 update for my Watch series 3.