Writing this down for my own sanity.

Required

1. Ethernet connection for Apple TV 4K.
2. Install Apple Configurator 2.
3. Assume Apple TV is already set up (but not provisioned).

Steps

1. Connect the Apple TV 4K via Ethernet.
2. Ensure that the Mac is on the same network as the Apple TV.
3. In Apple Configurator 2, unpair the Apple TV. Keep the pair screen open.
4. On the Apple TV, go to Settings > Reset to perform a factory reset.
5. Wait for the factory reset to complete.
6. Upon completion, the Apple TV will boot up. Do not touch the Apple TV remote.
7. In the Apple Configurator 2 pane you left open, pair the Apple TV again.
8. Once paired, click the Prepare button.
9. Check Supervise devices and Allow devices to pair with other computers. Uncheck everything else, then click Next.
10. Select Do not enroll in MDM and click Next.
11. Select the organization you wish to supervise the device, or create one.
12. Finally, select Show all steps and click Prepare.

Result

The Apple TV is supervised and ready to accept profiles, apps, etc.