I'm not sure which generation Apple TV we have where I am but it paired flawlessly. The Settings on Apple TV should show your watch and the watch will give you a code to type into the TV. I had the Apple TV remote handy to type in the code. Not sure how you would get the code in without the existing remote.
The watch will guide you through the steps. Did you open the remote app on the watch?
Strange, I tried it with 2 of our ATVs and both ATVs said the watch was paired, but the watch stayed on "add device." Home sharing is on, but it's not using the same apple ID as my iPhone/watch.
I guess I'll reboot my watch and try again.