My solution was totally different from other answers; I just needed to get the most recent iOS software update, which hadn't auto-updated because I didn't have enough remaining storage space.
So I cleared out some storage space via settings, got the software update on my iphone, reset my phone, reset my watch, went to the Watch app, and it worked perfectly from there.
I hope this helps!