I was literally trying to figure this thing out for about 4hours now and i stumbled upon this thread. Tried everything as well but this worked for me! For all of you who are still trying, please give this a shot! What i did was: Reset to factory settings the apple watch (mine was series 3) On iphone - uninstall watch app > reset network settings > connect to internet > reinstalled app> followed thread instruction > paired the watch then update started working! Or maybe you can just skip all of what I did and jump to threads instructions! Here's the thread but to save you time I will try to upload a photo. https://www.reddit.com/r/AppleWatch/comments/ix5pg9/series_4_unable_to_check_for_update_because_not/g6y1kaq?utm_source=share&utm_medium=web2x&context=3 Upvote so everyone can see! Wishing everyone a good day!