Hey guys, this issue had been driving me crazy for months on my Apple Watch Series 3 and I tried all of the other solutions on these pages, but they didn't work. Finally, I found out that all I had to do was go to Settings > Bluetooth and then forget my Apple Watch connection(Do this by tapping on the "i" symbol). My IPhone then created a new connection with my Apple Watch and then it started updating. I really hope this solves your Apple Watch update issue!