I've been wrestling with this same problem for weeks. One detail about my case is that the Apple Watch SE is a Family Setup device. Throughout the many hours of troubleshooting with Apple, every tech agent insisted that should not be a problem.
I was told in mid-January that this "Pairing Canceled" behavior was a known bug and would be fixed in the next release of watchOS. When that came out last week along with updates for Apple TV and iOS, I updated everything. That did not solve the issue.
Ultimately I decided to get an old iPhone and set up the Apple Watch again as a "normal" device, not a Family Setup device. This way the Watch and the iPhone are both signed into the same Apple ID. That fixed the problem right away.
HTH