I am on my fourth AW.
I had the same problem relative to the health app not being paired. I had to set it up as a new watch. Since I only had data in the health app for only about a month, I did not care about data loss. When I tried to restore from a backup (over air), I had all my data but still got the not paired status. Only setting it up as a new watch eliminated that.
Moreover, I had to select manual pairing without using the camera.
The whole thing is inconsistent. Over air backups of the iPhone, which has the watch data too are not encrypted. Yet, when I returned my previous watches to the Apple Store, for a replacement, they setup my new watch using a backup, which had my health data and yet I don’t think it was encrypted. Also when I returned the watches to the Apple store (three times ), they unoaired them, which should have removed them from my device list for my AppleID. Every Watch was still there. As I said before, the whole process is inconsistent.