Have the same problem) Tried everything, changing network, provider, changing region, language, time, even different devices.

I have resolved this problem. First of all, when you connect your device DON'T RESTART after first enrolling. After that in ABM you need transfer your device to your MDM server. After that you need (in my case this is Jamf) bind in PreStage Enrollments, than waiting when device will be Assigned. After that you need restart you device.