I had the same issue. My Macbook would show up in the list of devices in the ATV settings menu but would not be recognized by Xcode. My ATV is connected with an ethernet cable. For me this worked by a weird combination of the following:
Removing my mac from the list of Remote App and Devices in the ATV settings
Disconnecting the ethernet cable and connecting to WiFi on ATV
Quit/restart Xcode and toggle WiFi on/off on my Macbook a couple of times
Tried to pair about 15 times, after toggling WiFi on/off on my Mac it suddenly started working