UPDATE: After crosschecking the two Marshmallow systems I found that in mine there was a libbluetooth.qualcomm.so that redirected to a libz2_bt_patch.so. Don't know where that comes from and just deleted the link. Seems as if this cured the problem as it connected flawlessly after that. Will try again though tomorrow.
So currently no need for you to investigate further