After trying everything which was described here and on other forums I finally made it work, and I am soooo angry with Apple!
First I should say that most probably there are different issues which may cause this problem with the internet connection (wi-fi bands, ios compatability, real connection issues at least).
I had this issue pairing iPhone 11 and iWatch 3 which was not used for ~ a year. First I tried the accepted answer, then I tried Beem355i's tutorial for multiple times. Then I tried updated Beem355i's tutorials from other users here. I also read other forums, I finally contacted Apple.
After several questions I was provided a reply that this happens when I have a too low iOS on my watch (5) and too high iOS on my phone (14). So I need to find a device with iOS 12, pair my watch, update its iOS, unpair, and then I will be able to pair it with my iPhone 11. How would you rate the ridiculousness of the situation? Of course, I don't have an old iPhone, so they suggested me to take the watch to a service center.
I googled it, and they ask for 250$ for the repair!!
I was desperate, I decided that sometime later when we are back to normal (afterCovid) daily working routine, I would ask around in the office if smn has iOS12 or earlier device and is ready to help me.
My final decision was to read through all the posts here, and I found the one from @mochimilk:
I tried absolutely everything to get my watch to pair and I was about at my wits end; but all I had to do was change my region to Canada on my phone and watch and it started to update. Such a pain! Hope it works for all of you as well.
I tried it too, I changed from Austria to Canada, and it worked! Now my watch is in the process of update.
It is definitely a software limitation, worst of all it is based on your chosen region...
So if all the guides do not work for you, try changing the region. I am not sure if just changing the region alone works, because I have tried any other possible steps (even resetting wi-fi) before this change, but anyway, there is hope. Keep trying.
I solved this issue by uninstalling the Watch app from my iphone and reloading it. After reloading the app I paired the watch to the phone and the update started loading.
I will say one thing today was a frustrating day trying to get the watch to pair for a few hours. Finally I have success. My fix is the same as many but it took only one try when I changed the Country and Language. I decided to use language Portuguese, and country Afghanistan. It worked. so mad I could not see straight. But success, hope it works for you. It will.
Apple Watch 3, iPhone 11Pro w/ iOS 14.6 - nothing works to update the watch and make it a usable device, it's basically a dud now. I've tried resetting the iPhone and trying to update the watch in different language. No dice!