(After some more hours of debugging) The error is caused by SELinux policies.
sudo getenforce
shows enforced
, i.e., SELinux is on. After turning it off via sudo setenforce 0
it is possible to print. I found some documentation by Brother that has some guidance on how to keep SELinux enabled and still being able to print. It involves adding some policies and re-applying them to the installed driver files.