CompanionDeviceManager Bluetooth dialogue is not shown on Fossil Gen 6 with Wear OS 3 / Android 11

Question

I have two apps with very similar code base working fine on mobile (Android 13 / API 33) and wear (Android 11 / API level 30) with the old style Bluetooth connection procedure. When trying to publish on Playstore, I was requested to rework this procedure to use the CompanionDeviceManager to reduce the number of requested permissions. The rework of the mobile app was reasonably easy, the app is working fine again with the CompanionDeviceManager. The wear app though is giving me a rather hard time, the CompanionDeviceManager Bluetooth dialogue does not show.

I've been browsing and reading and trying, but all the combinations of code and permissions I've tried end with CompanionDeviceManager.associate calling checkFeaturePresent, which returns false with debug output "Feature PackageManager.FEATURE_COMPANION_DEVICE_SETUP not available" despite the corresponding permission being added to the manifest file. The taget device is a Fossil Gen 6 smartwatch. The device I need to connect to is a BLE device, but I don't think that's all that relevant.

I'm getting a bit desperate here, so any pointers are much appreciated!

Permissions in Manifest (not all of these should be necessary):

    <uses-feature
        android:name="android.hardware.type.watch"
        android:required="true" />

    <uses-feature
        android:name="android.software.companion_device_setup"
        android:required="true" />

    <uses-permission android:name="android.permission.REQUEST_COMPANION_START_FOREGROUND_SERVICES_FROM_BACKGROUND" />
    <uses-permission android:name="android.permission.REQUEST_COMPANION_RUN_IN_BACKGROUND" />
    <uses-permission android:name="android.permission.REQUEST_COMPANION_USE_DATA_IN_BACKGROUND" />

    <uses-permission android:name="android.permission.ACCESS_COARSE_LOCATION" />
    <uses-permission android:name="android.permission.ACCESS_FINE_LOCATION" />
    <uses-permission android:name="android.permission.ACCESS_BACKGROUND_LOCATION" />

Code of Activity supposed to trigger the CompanionDeviceManager dialogue:

    @SuppressLint("MissingPermission")
    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        setContentView(R.layout.activity_ble_bond_cdm_activity)

        val deviceFilter: BluetoothLeDeviceFilter = BluetoothLeDeviceFilter.Builder()
            .setNamePattern(Pattern.compile("${MainActivity.productName}_\\d+"))
            .build()

        val pairingRequest: AssociationRequest = AssociationRequest.Builder()
            .addDeviceFilter(deviceFilter)
            .setSingleDevice(false)
            .build()

        deviceManager.associate(
            pairingRequest,
            object : CompanionDeviceManager.Callback() {
                override fun onDeviceFound(chooserLauncher: IntentSender) {
                    startIntentSenderForResult(
                        chooserLauncher,
                        SELECT_DEVICE_REQUEST_CODE,
                        null,
                        0,
                        0,
                        0
                    )
                }

                override fun onFailure(error: CharSequence?) {
                    MainActivity.setSensorDevice(null)
                }
            }, null
        )
    } // onCreate


    @SuppressLint("MissingPermission")
    override fun onActivityResult(
        requestCode: Int,
        resultCode: Int,
        data: Intent?
    ) {
        super.onActivityResult(requestCode, resultCode, data)

        when (requestCode) {
            SELECT_DEVICE_REQUEST_CODE -> {
                when (resultCode) {
                    Activity.RESULT_OK -> {
                        val scanResult: ScanResult? = data?.getParcelableExtra(
                            CompanionDeviceManager.EXTRA_DEVICE
                        )
                        // The user chose to pair the app with a Bluetooth device.
                        if (scanResult != null) {
                            MainActivity.setSensorDevice(scanResult.device)
                        } else {
                            MainActivity.setSensorDevice(null)
                        }
                    }

                    else -> {
                        MainActivity.setSensorDevice(null)
                    }
                }
            }

            else -> {
                MainActivity.setSensorDevice(null)
            }
        }

        finish()
    } // onActivityResult