Thanks, Carl!
Your proposal is definitely on the right track. Unfortunately, though, I'm having some difficulty implementing it.
I have set the new paragraph style to German language spelling and have set the font characteristics as shown in the first attachment (no change to all parameters). However, when I run a find and replace, the text ends up being deleted and I am left with a lot of text frames with no text in them.
Interestingly, if I run the same find and replace with the text size set to, say, 12pt, (second attachment) then the language is indeed changed to German, but of course all the text is then converted to 12 pt throughout the document.
I'm not sure what is going on there.