So I recently purchased an Apple TV and was having this same issue. I got this to work by manually downloading the latest "support file" for the version of tvOS installed, which was 15.4 (although the latest version released at the time of writing was 15.6).
It connected successfully on the first attempt. I'd suggest giving this a try.
Download and extract if necessary, copy extracted folder to: /Contents/Developer/Platforms/AppleTVOS.platform/DeviceSupport/.
hopefully this helps