When using conditional access along with Intune licensing, Teams Desktop Phones must be enrolled to Intune. If you're receiving errors on your phone about enrolling a device in Intune, you'll need to follow the steps in the document below.
Please note that you will also need to make sure your phone is on an up to date firmware version. Since the phone won't be available to update through the Teams Admin Center, you'll need to follow documentation from the device manufacturer to update your phone to the most recent firmware version.
You should also verify that the user attempting to sign into the phone hasn't reached their maximum number of enrolled devices.
Login here https://endpoint.microsoft.com/ using a 365 Global Administrator account
Go to Devices>Enroll Devices>Corporate device Identifiers
Click Add>Enter manually
Click the drop down and select Serial number
Locate the Serial number on the back of the Teams phone and enter it as shown in the example below.
Please note this example is a Yealink Phone. Poly Phones use the MAC Address as the serial number.
Once the phones are finished adding here click the Add button at the bottom left.
You have now successfully enrolled the Teams Phone and the end user can now sign in.
Microsoft Article for reference
Deploy Teams phones, Teams displays, Teams panels, and Microsoft Teams Rooms on Android using Intune - Microsoft Teams | Microsoft Docs