is company portal already installed on the new device, is the device, and user, current in your azure directory?

To register a new device with Device compliance, you need to deploy a company portal first create a policy with Register Azure payload, and made it available in Self Service, and use the Self Service to execute the policy to register your device to azure Via Company portal 

That is what I thought and have setup but it didn't work.

Recreating the policy.