It turns out you also have to add the UDID of the Apple Watch to the Apple Developer Portal, and update your Development provisioning profile to include this UDID.
The UDID can be obtained in Devices window of Xcode. After pairing, the info of the Apple Watch will automatically display below the info of your iPhone.
At the time of writing, this seems to be documented nowhere, and the error message on the Apple Watch wasn't particularly helpful. So I wish this try-and-error lesson would save you some hassle.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…