I also experienced this problem with an Apple Watch Series 4 that I have purchased for my daughter for Family Setup. I have two iPhones 11 Pro Max at home, being mine on 14.5 Beta 8 and my wife's at 14.4.2. None of the iPhones would find an update for the watch with the same error everybody on this thread experienced. I was trying to pair it on a Family Setup with both iPhones. When I decided to try to set it up as a my personal watch, the update was found and started downloading. It seems the watch was on a version prior to 6.3, as this is the update that is downloading at this moment. I'll update this post once the watch is fully setup.