Hi
As your Apple Watch has not be unpaired as expected when unpairing via the Watch app, you will instead need to erase it manually before being able to re-pair it to your iPhone:
On your Apple Watch: when viewing the time, go to the Home screen (via a single press of the Digital Crown) > Settings (gear icon) > General > Reset > Erase all Content and Settings > confirm when prompted.
Then follow the instructions here to re-pair it with your iPhone, including first checking that your iPhone is updated to the latest version of iOS and choosing to Restore from Backup if offered the option during set up of your Apple Watch:
Set up your Apple Watch - Apple Support
More information:
Unpair your Apple Watch and iPhone - Apple Support