After trying several solutions proposed in this forum, the solution that finally worked for me is hard resetting your iPhone. If you have an iPhone X or later (with no home button), follow these steps : click volume up button once click volume down button once click and maintain the lock button (on the right side) until the power goes off and the Apple logo appears. This will refresh all the software on your phone. After that, reset your Apple Watch, and start pairing it with your iPhone, you should see the software download bar, this may take a long time but right after it, you'll have the latest software updated and your Apple Watch up and running.