Not exactly sure which solution worked for me but the things I tried were:
reset my watch
turning off my VPN
deleting the watch app
hard reset on my phone
Re downloading the watch app
I did all these in that order and paired my watch again and it worked - didn’t even have to wait and install the software again, it took me right to the installation.
prior to this I tried the suggestions in this thread including changing my language and country and that didn’t work for me.