The issue was that Enable Bluetooth gateway was enabled in Shelly’s UI. Shelly’s DEBUG log read Unable to start OH-BLU Scanner, make sure Shelly Gateway Support is disabled in device config.
I turned it off, as you suggested here (Shelly Binding - #3771 by markus7017), and now everything seems to work as it should.
I think it would be better if the binding documentation explicitly instructs users to disable Enable Bluetooth gateway. If you want, I can try to make a PR with changes to the README?