My input isn't going to be very useful but as a point of data, I've never had trouble with my 8bitdo controllers and Linux.
Sometimes they don't pair right away on the Switch, but Linux has been fine.
Now I'm trying to remember which controller I used to test Yuzu...

Weird as it is, I've heard launching games through Steam Big Picture mode with the controller connected can help but that might just be more a key mapping thing than anything else.

Try running bluetoothctl from the commandline and playing around with it. This article is for Gentoo but you can go through the manual steps in "Device pairing" and maybe you'll be able to identify the issue.

Looking at bluetooth logs could also be useful. If the service is called bluetooth on Mint, try running:

journalctl -u bluetooth

Try to mark the devices as trusted in blueman and see if it helps.

Not a Linux user but I had a lot of problems with the sn30 pro plus connecting to bluetooth when I first got it. The issue was something in the controller bios. It'd cause my entire system to spaz out. I had to roll back to the first version to fix it. So maybe try messing around with bios versions if you can to see if that fixes it.