I tried all procedures from https://www.wipelock.com/phone-tips/apple-watch-unable-check-update/ and others, but nothing worked for me. So I tried to follow the steps that @jwongthecity posted and it worked to me (very simple procedure). After reset and erase all data from the apple watch, I turned off the Wifi on iPhone before start pairing and left only LTE Data (3g/4g/5g data) on (Apple watch won't be able to download the update by LTE) Once in pairing, click on "Update" and wait some seconds to the apple watch make the activation After that, the screen will show "Checking for Updates..." but nothing is happening because the WiFi is still turned off So go ahead and turn your WiFi back on your iPhone The update will picked up and FINALLY my apple watch and phone are paired Thanks man!