You will need to know if France required exit permits at that time. You will also have to estimate when births and marriages took place, then find out who rules at those times. At that time, Germany wasn't a united country, so which kingdom were then in if they were under German rule? Also, check records in the appropriate church (Catholic or Protestant) in the area where they lived. That might actually be your best place to start.
I hired someone to find my German ancestors location; he was able to find a birth certificate, one sister's birth certificate in the same place, and the parents marriage record in under one hour from using films in Salt Lake City. You may want to fined them yourself, but a little professional help could put you in the correct place to start. I am only an educated intermediate researcher; I only know how and where I have found the information I wanted.