Yes, VPNs are legal in Germany. What isn't legal, is using VPNs to carry out a crime or illicit activities.