After many attempts, I managed to pair the ATV with Xcode. Not sure exactly what I did different finally. Turning Wifi off, then on, unplugging ethernet from the ATV, unplugging the power cable, etc. Rebooted my Mac. Finally working.

Bumping this. I'm having the same issues. (reinstalling TVOS, re-pairing the ATV, etc don't work).