Here's exactly how I did it:
1- Go to the Watch-app on your iPhone, go to 'General', scroll to the bottom and erase all content and settings from your Apple Watch
2- Connect your iPhone to your Mac/PC and backup your iPhone to iTunes
3- Go to the settings on your iPhone, 'General', scroll to the bottom and press 'Erase all settings', NOT erase all content.
4- The phone reboots, then I set the iPhone up as a new Phone (General, scroll to the bottom and press 'Erase All Content and Settings')
5- iPhone will restart, when It's ready, pair your iPhone with your Watch. You can download an iPhone app like Swarm to test if the native apps work on the Watch, they should work.
6- Erase all Content and Settings from your Watch using the Settings on the Watch.
7- Erase all Content and Settings from your iPhone using the Settings on the iPhone.
8- Your iPhone will reboot, restore your iPhone from the backup you made in iTunes.
9- Pair your Watch as a new Watch, not from a backup.