I've had the pleasure of corresponding with Bernd at some length in the relatively recent past; he's a fine fellow with his heart in the right place, but he's extremely busy too as the CEO of his own very high tech firm and consequently quite tardy as to the delivery of requested materials; I know, as I've been waiting a year or so for him to get me certain data that I had asked him for. But I wouldn't necessarily rely on him in your case, as it appears that you've got most of the pertinent data already at hand, i.e., the names and place and years of birth of your 2nd great-grandparents.
As they were born during the period of the annexation of the Palatinate by the 1st French Republic, they should be entered amongst the earliest civil records, initiated under revolutionary France, of their hometown; consequently, I'd suggest that you start with the Registrar's Office, if not in Medard itself, given its small size, then perhaps in Meisenheim - a letter to said office in the former location might even be forwarded to the latter, or to whichever is the directly responsible administrative centre, by the Bundespost as a matter of course - and with the information which you should be able to obtain there, you could then proceed with some confidence to the books of the relevant church community, whether Lauterecken or another, in order to pursue their ancestry.
Know, however, that Meisenheim prior to the Napoléonic period was a significant administrative centre of the Dutchy of Pfalz-Zweibrücken, which was dissolved during the French occupation. Indeed, my own 6th great-grandfather, Wilhelm Ludwig Schuck of nearby Obermoschel, obtained his master's training in that city. My line had all been adherents of Evangelism, however, as were, I believe, another line of Schucks from also nearby Odernheim who ultimately settled in Moschel as well - Wilhelm Ludwig's father originally hailed from Krähenberg in the general vicinity of Zweibücken, his having migrated to O'moschel in the early 17th cent.
One final thought: Theodore and Elizabeth are obviously anglicized given names. You might want to approach the Registrar's Office with the German spellings, i.e., Theodor and Elisabeth(a).