I have implemented Companion device pairing and it works great for most devices without requiring any location permission or location services enabled. However, we found for example Xiaomi Redmi Note 10 Pro (Android 11) where the BLE scan timeouts when Location services are disabled.
In my opinion the Companion Device feature was implemented and designed in a rush. You could expect bugs like the "Location services" must be turned on and the Companion Device pairing dialog doesn't warn when it is not enabled. Until Xiaomi or Google fixes this bug, you will need to have workarounds in your app, for example telling the user to first enable Location services if you think that will be needed.