It's actually the opposite: I chose a keyword combination that is so rare that I do not have any competition (my name is one of the keywords, for example - there is not competition for it as there seems to be only one other person in the world with the same name as me)
so, it can;t be that I do not rank for those keywords becasue they are too competitive.
As to my site not being popular enough: the english version always appeared in the serp a day or two after they were indexed - all in a matter of a few days or even only one day. It's just the German translation that cannot be found at all.
I have plenty of links to the englisch pages. The German pages have the same urls as the english pages with a /de at the end. (www.eample.com/de) I am not sure if they share the links with their sister english pages.
I never had to have links to my new english pages for them to appear in serps - so I am not sure why the German pages should need links to rank at all (not well, I understand, but they should be found in the search engines)
About it's taking time: its been 4 whole weeks. Is it possible that it takes so long?