After googling some time around, I found the solution to translate the Caroline theme. For the next time (and also for others having the same problem), here a short HowTo.
First of all, there are a lot of translations available, also for Coraline: http://translate.wordpress.com/projects/wpcom/themes/coraline/ and if there is nothing for your language it would be great if you do you translation here to help comunity.
After you have selected your language, you can export the translation by choosing
“Only matching the filter” as “Portable Object Message Catalog (.po)” on hte bottom of the page. Now press Export and store the downloaded file. You have to rename the file to fit to your language, in my case this was German and I renamed it to de_DE.mo. The file has to be uploaded to the Themes language directory, in my case this was: wp-content/themes/coraline/languages and after reloading the Frontend the translation is visible. Sometimes you have to ensure your Blog is switched to the correct language if this is not working as expected. In my case I have a line in my wp-config.php file which is: define(‘WPLANG’, ‘de_DE’);