So: I tried to reinstall Recalbox 6.1.1 from scratch all over again. 8bitdo pairing suffering from the same problems (cant pair). Tried to pair manually via bluetoothctl, it WORKS - but does not keep paired after a reboot.
I honestly do not know what to do anymore. Cant find older version (6.0) anywhere anymore and 6.1.1 is useless for me if I cant keep my gamepads paired.
If someone have any solutions for this, please let me know.