@Damian Wojtas , After researching, I find this is a known issue with Samsung device. Here is a link with more details.
https://docs.samsungknox.com/dev/knox-sdk/faqs/installation/what-does-security-policy-prevents-app-installation-mean.htm
Note: Non-Microsoft link, just for the reference.
Here, please remove your previous enrolled device from both Intune and Azure AD portal. And then disable the Device Administrator from Settings > Security > Device Administrators, After that, enroll again to see if it works.
However, if the issue still persists, please contact Samsung support to help on this.
Thanks for your understanding and have a nice day!
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.