You can probably update your Apple Watch either using the paired iPhone, -or- direct on air from Internet. The requirements are slightly different, but documented in
Update your Apple Watch - Apple Support
You will also find additional links in the support document for problem solving. However, there are two regular causes of problems;
The Apple Watch must be on charger power, even if the battery is fully charged.
The required WiFi connection is a regular (home or office) WiFi, NOT a hotspot from another cellular device, and not one of those horrible public WiFi systems with a web landing page and login (You often get these in hotels and places like coffee stores)
Also please check whether it says "paused" or is that your interpretation because sometimes the download and checking can be very slow and look like the process has stopped. If that happens just be patient and check again a few hours later (or even overnight!).