It had me in stitches when I first heard and I really wondered how big a fraction of his audience got that one.

A fairly intellectual audience, in the 50s and 60s when the space race was big news and von Braun's Nazi past was recent history? I'd guess a majority.

Is there a specific joke in "Nazi Schmazi" besides the general idea that he wasn't picky about what regime he worked for?

Yiddish

Ah, I am so used to that as a general wordplay pattern that I didn't think about the origin, good point!

Do you mean it sounds like it could be a Yiddish word? Because it doesn't seem to be an actual Yiddish (or German) word, as far as I can tell.