I had issues enrolling 4th Gen apple tvs as well. I am using Apple Configurator 2. No errors when dropping both my enrollment and trust profiles. Able to add the wireless profile without issue and devices connect using this. We are running JSS version 9.
Was able to finally get the devices enrolled by making sure to have ethernet connected. For whatever reason was unable to get devices enrolled with wifi.

Hi

I had exactly the same error message today: [ConfigurationUtilityKit.error - 0x4 (4)]

Trying to install a Profile with a Wifi payload onto an Apple TV 4 with tvOS 10.0.0.1.

Were you able to solve it?

@dwynne : So, for you, attaching an ethernet cable to your network during installation worked?

Thanks for any help!
Christian.

Yes, the only way we could reliability enroll an apple tv was to connect to ethernet during the profile drop.