With the exception of not seeing any error on Step 3, I'm experiencing the same issues.
The pairing fails (sometimes) but the Apple TV still shows up. I select Prepare to add it to ASM, it appears to work, wipes/reloads the Apple TV but it doesn't add it to ASM. It disappears from Configurator but still shows up under Paired Devices as not connected. Then I have to remove it from Paired Devices, reboot the MacBook and pair it again in order to start over.
Also, I am ONLY trying to add it to ASM, not enroll it into MDM yet.