There’s a limit to the amount of devices you can register for the Intune Company Portal app.
To fix this, yes you’ll need to remove a device attached to your account. This is not done via Outlook for Web, where you can remove devices – that’s purely for Outlook. It’s also not done via https://myaccount.microsoft.com/device-list as it’s not removing it from Azure.
As per Microsoft Documentation , there’s Intune device limits, and Azure device limits. Intune / EndPoint Manager has a maximum of 15 devices, where Azure has a default of 20, but can be changed to a few different values, including ‘unlimited’.
To remove devices from a user, and admin should use Azure Active Directory and go to Users > Find the user > then under Manage, choose ‘Devices’. Any old device (check by the activity date) can be selected and deleted.
After removing enough devices here, you should be able to register the new device via the Intune Company Portal app again – and in my testing, this was next to instant.