Downloaded and tested the example as-is. It works properly on Android 16.
You do need to give the app the "allow always access" which can be a bit confusing to set.
And you should of course run it in release mode. And check the logs, it should look like this after a restart:
--------- beginning of main
*** Receiver (startatbootreceiver) Receive (first time) ***
*** Service (starter) Create ***
** Service (starter) Start **
** Service (tracker) Create **
** Service (tracker) Start **