This question is a tricky one, because it is not completely regulated how patronyms should be used in Germany. I'm also a foreigner living in Germany, and accidentally got my patronym saved in the Melderegister through the process of obtaining a birth certificate for my son (Melderegister got my patronym from Standesamt).
I immediately asked the Melderegister employees to remove my patronym from the registry and set it back into accordance with my travel passport (Reisepass). Unfortunately, they rejected my request, because there was a regulation that they need to follow the naming from Standesamt.
Since I'm not a German citizen, I decided that I do not care anymore about the Melderegister, since it has no influence on my non-German passport, which is my main ID in Germany (there my patronym is not written in Latin). My argumentation is that I'm a foreign citizen, I haven't applied for name change in Germany, and only me and my home country, which issued the passport, can decide how my name should be written and used in Latin.
UPDATE: Indeed, there is a document regulating the "Meldewesen" (registration processes) that states that foreigners who do not have any German documents issued from the registry office (Personenstandsurkunde von Standesamt), the form of the name in the passport is determinative ("Bei Ausländern, die keine deutsche Personenstandsurkunde vorlegen können, ist die Eintragung im Pass maßgeblich"). The question is only if they now consider the birth certificate of my son, where also my father's name is written, as such a document, which is probably the case.
Alternatively, one may go to a court in order to try removing the father's name from Melderegister.
Since then, from time to time I also see the my patronym (Vatersname) in some German documents. So far this never was a problem for me.
UPDATE 2: After 8 years, I finally succeeded in removing patronym from Melderegister (using the argumentation above)! Now it is again synchronised with my passport, and not with Standesamt!
Please note that according to the information above, it is only possible until you won't get a German Personenstandsurkunde issued for you. For me, I argued, that the birth certificate of my son is his document and not mine! So they cannot threat his certificate as mine to override how my name is written in my passport.
Still, if you do not want to fight for it with them:
When getting a residence permit, you may simply ask Ausländerbehörde to copy your name from your main ID, which is your passport (if it is written in Latin without father's name there) and by no way a Melderigister! I did this several times already.
More info (contradicting my answer) about this topic: