@bananapatata From my understanding and testing (when DEP enrollment for Apple TVs first came out) Apple Configurator 2 can no longer be used to enroll Apple TVs once they belong to a DEP environment, they will return an error. Not sure if this has changed or not, you can try it out and see what happens.
Sorry if this is a stupid question, but you've tried completely resetting the Apple TV and going through the enrollment again right? If you have "Require Credentials for Enrollment", then you should be seeing a screen asking to sign in during the setup assistant. If you aren't seeing that, then the prestage profile isn't getting to the Apple TV correctly.
You could also try to rescope the prestage to the device? Uncheck the device in the prestage, save it, then check the device again and save it, then wipe the device to try to enroll it again? Not sure if this would help.