Do it using JS. Grab the class of the error message, and change it's content for whereever it appears.
var myClasses = document.getElementsByClassName("wpcf7-not-valid-tip");
for (var i = 0; i < myClasses.length; i++) {
myClasses[i].innerHTML = "Bitte füllen Sie das Pflichtfeld aus.";
}