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

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.