In Windows Server 2012 R2 ist es leider nicht mehr so einfach über die Oberfläche möglich die Einstufung der Netzwerk-Kategorie zu ändern, wie dies noch unter Windows 7 möglich ist (siehe hier bei TippScout).
Glücklicherweise habe ich in Haikos Blog den entsprechenden Tipp gefunden, wie es über die PowerShell funktioniert:
Get-NetConnectionProfile
Set-NetConnectionProfile –InterfaceInxe # –NetworkCategory Private
Für das #-Zeichen muss der verwendete Index-Wert angegeben werden, den man aus der Ausgabe des ersten Befehls bekommt:

Danach ist das Netzwerk entsprechend eingestellt …

… und es funktioniert auch wieder die Remote-Desktop-Verbindung.
Danke Heiko