For what it's worth I asked an Apple employee at the Leicester store in the UK this question on Weds 21st Dec and he said they do not pair with Apple TV 4. He did let me have a listen to them though, very impressed with the sound, especially the bass response, they are much better than the standard wired apple headphones. They did feel like they would fall out of my ear if running etc though...
I've got some arriving tomorrow so will check and report back...
UPDATE:
They don't pair automatically through iCloud, although I think that was expected given no reference to aTV in the release notes. Pretty simple to add as a Bluetooth device though. Into the Settings, Remote and Devices, and then press the hidden button on the Airpods case and they're added to the aTV.