Try rebooting your router/networking equipment. Pairing and connecting with the AppleTV happens over Bonjour/mDNS and sometimes that can get into a bad state with multiple entries for the same device.
I had gotten into the same bad state where the pairing process never completed. Tried rebooting the TV and my Mac with no help. Everything started working as expected when I restarted my router.
Tekgo
Users receive reputation points by contributing quality content to the forums.
Posts include post and replies published on the forums.
Post authors can mark replies as Accepted to indicate successful solutions.
Apple Developer Forums admins can mark replies as Apple Recommended to indicate an approved solution