So I tried Beem5i's suggestions and I honestly think the bugger here is Low Power Mode.
I was about to give up and then after I attempted all his steps, go into Settings Battery.
Turn on Lower Power Mode and attempt to pair watch again. It randomly then started updating! Apple software is some of the best, but this is a huge bug.