I figured out the problem. The problem is that the Apple Watch you are trying to pair again already exists in your iCloud device list. To fix this go to (on your iPhone) Setting -> click on your name and then there is a list of devices ever associated with you Apple ID on your account. Remove the Apple Watch you are trying to pair again. Bam! Update will work. It may say you have to update your phone. Follow the link even if your phone doesn’t need an update then go back to the watch app and boom it will start updating.