Nothing worked for me so far... tried following options... hard resetting iphone hard resetting apple watch switching to mobile internet instead of wifi switching to 2.5 ghz wifi from 5 ghz wifi changing region to Canada/English (correct for my app store account and physical location) device details: watch 4 with iphone xr running 14.4

I have finally resolved the issue... none of the advised steps resolves the issue but i would say i probably ran into an edge case... i was on an USA cellphone service provider while on Canadian soil with App Store canada account and that apparently caused the issue (and yes connecting to wifi did not fix the download-update issue). For me it was rather a tricky and funny fix... tried to pair the apple watch with a different iphone on Canadian network. update of the watch OS worked this time quit after finishing update tried to pair with the previous phone once again and this time pairing process went directly to the next step without asking for update and pairing worked.