In Germany, you instead 'hit two flies with one swatter', an expression which native speakers of English wouldn't recognize as proverbial but rather take literally.
I completely disagree. While there are indeed many proverbial idioms that don't translate well, that's certainly not one of them.
The two-for-one deal being mentioned makes the analogy with "kill two birds with one stone" glaringly obvious. I'm sure most English speakers would have no trouble picking up the meaning of it in context, recognizing that the speaker was foreign, and that the phrase is probably the analog of the English version in whatever country he or she is from. It might even elicit a giggle or two.