Hey everyone!
Was pairing replaced S4 watch with my 12ProMax today, got that annoying message.
Tried resets, reboots, wifi router reset.
Tried unlinking iCloud, as @Beem335i writes.
No luck.
But then - I went to iPhones Settings and made Network Reset. And boom!
Hope that helps anyone.