Hi Fabian! I assume that your VMs are local Hyper-V only, not in Azure infrastructure, right?
Based on my experience, that modern Settings -> Remote Desktop OFF settings does not have actual meaning. In my Intune Cloud-only enviroment RDP works fine this setting being turned off. But what you need to check is this:
This must be enabled and policy affecting this is:
Another object you need to control is firewall. If you have MS Security Baseline in place, your local Firewall rules are not honored by default (you can create them but effect is 0), because in baseline, merging Intune and local firewall rules are not allowed. I explain this in more details here: https://www.linkedin.com/pulse/intune-security-baselines-firewall-rules-pavel-mirochnitchenko
And when creating Firewall rules in Intune, as surprise, you need to identify TCP and UDP ports separably, ANY protocol rule does not work. Here is my RDP rules in Intune.
Specifying Protocol is important here. Do same for UDP. Also please be informed, that with this setup I only connect physical machines, not virtual. I haven't test this with VMs but is should work.