Did you try to install the Weather Complication using a different Watch face?
The Weather App is working on your iPhone and on your iPhone, the iPhone is mirrored in WatchApp/Weather, and the Default City is set to "Current Location"?
Also check on your iPhone/Settings/Privacy & Security/Location Services/Weather -> While Using the App should be enabled as well as "Precise Location"
Did you already try to force restart your iPhone and Apple Watch, instead of shutting down and restarting?
Force restart iPhone - Apple Support
To force restart your watch, press and hold the Digital Crown and the Side button together for about 10sec, until the Apple logo comes back again.