<loc>"http://domain.com/de/mensfashion"</loc>
<xhtml:link rel="alternate" hreflang="fr" href="http://domain.com/fr/mensfashion"/>
...

Mage::app()->setCurrentStore($de_store_id);
Mage::getModel('catalog/category')->load($category_id)->getUrl();

Mage::app()->setCurrentStore($fr_store_id);

Mage::getModel('catalog/category')->setStoreId($fr_store_id)->load($category_id);

$initialEnvironmentInfo = $appEmulation->startEnvironmentEmulation($fr_store_id);