For all of you who are struggeling with this situation i made a workaound like this:
I added all those values to the affected database tables directly. This is for sure a quick and dirty way, but it does the job.
For all in need of some ideas here is the (undocumented) snipped belonging to my initial post.
// Get values for next language insert
$entity_type_id = $category
->getResource()
->getTypeId();
$entity_id = $category->getEntityId();
$read_entity = Mage::getSingleton('core/resource')
->getConnection('core_write');
$sql_entity = "SELECT * FROM eav_attribute WHERE
`attribute_code` = 'name' AND
`entity_type_id` = " . $entity_type_id . ";";
$row_entity = $read_entity
->fetchRow($sql_entity);
$attribute_id = $row_entity['attribute_id'];
// prepare value for name field in different langauge
$val = Mage::getSingleton('core/resource')
->getConnection('default_write')
->quote($v['en']);
$sql_insert = "INSERT INTO `catalog_category_entity_varchar`
(`entity_type_id`,`attribute_id`,`store_id`,`entity_id`,`value`)
VALUES ($entity_type_id,$attribute_id,$storeId,$entity_id,$val);";
$read_entity->query($sql_insert);
I hope this helps someone out who is in need of this.