The device registration errors in Microsoft Intune can be misleading. I was getting This service is not supported, MdmAuthorityNotDefined, A connection to the server could not be established etc errors during an Apple device enrollment. This was my test device. I have used this device with different user account, Intune subscription etc.
Possible issue #1
In my case, the following 2 errors were due to duplicate/already enrolled device information in Intune. Everything started working once I removed the existing device entry from Intune.
Device not added
This service is not supported
Profile Installation Failed
A connection to the server could not be established
Possible issue #2
In this case, the user was not part of the Intune collection. You can see the current configuration from SCCM->Intune subscription properties.