Hello, to anyone still searching for answers I’ve been at this for months but recently today for hours I’ve even been on the phone with apple’s technician. I’m due for a call back in 15 minutes they asked me to try & connect my watch to another phone, however my other phone was locked after attempting to unlock it from iTunes so I could connect my watch to the other phone. I ended up needing to use find my iPhone. I actually still had my old device in my find my iPhone app. So I went to forget that device & it instantly let me pair my watch with my current phone. I highly suggest that. When you erase that device from your find my iPhone app it actually drops everything you ever had paired to the device & that was what causing me from not being able to pair & my internet to “connect” for the update! hope this helps