Android Corp Devices Locate Device Greyed Out

Make sure the device is enrolled as a dedicated device, fully managed or corporate-owned (not personally owned). You can change the ownership type from Personal to Corporate in the Properties blade of the device after enrollment.

Also check if the location services are enabled on the device (with a work profile the Intune app on the device needs to have the location permission enabled / allowed "all the time". I'm not sure if this can be set with an app configuration policy though, so you might need to set it manually on the device)
https://learn.microsoft.com/en-us/intune/intune-service/remote-actions/device-locate#supported-platforms

Your device restriction settings are correct but you could also check if that the device has checked in and has the configuration profile settings applied successfully.