When using conditional access along with Intune licensing, Teams Desktop Phones must be enrolled to Intune.
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