So i had similar issue with Apple Watch 3. Just couldn’t update as same error kept popping up again and again after trying all resorts mentioned below except complete reset which I wasn’t very confident to do due to fear of losing data. So what worked for me - Had a spare iPhone SE sitting in the storage. Ran a full reset on it, set it up again and reset the watch by pressing on/off button for more than 30 seconds after apple logo appears and IT WORKED. Just couldn’t believe it. Apple support over the chat & phone wasn’t able to do much either. I hope this helps someone who went through same problem and felt like throwing away the watch in the bin ✌🏼