These inquiries have been around for a while.
Given that the family spent time in WW2 and Post WW2 Germany, an inquiry at Bad Arolsen, should be helpful. Germans kept detailed records of anyone who set foot on their territory. Bad Arolsen contains appx 5/6 miles of DP (Displaced Peope) documents, that are still being digitized. You should be able to get a copy of all documents generated by your DP Family, including personal info like exact place of birth and copy of Grandparents' marriage certificate, etc. Inquiry is available at no cost to immediate family. All you have to do is submit Baba and Dido's full names and any transliterational (sounds like) name variants and their exact birth dates. You can perform inquiry for both at the same time. Additionally, include the names of children born in Germany. Response can come in three days or three months. Make sure to provide your full snail mail address with your email address.
Click on to FAMILY INQUIRIES AND REQUEST FORMS:http://www.its-arolsen.org/en/archives/index.html
Once you get a response, feel free to contact me and I can then help you move your inquiry to Ukraine.