I’ve also thought about it the last days and I think the easiest way would be to do it like you translate a normal wiki page: add the languages template on the main page (between and ), copy the original template to the language namespace and translate all the strings which should be translated.
The small disadvantage of this method is that you have to use the full template-name including the language-prefix ( {{xx:Template:abc}} ) but you also have to use a language-prefix when you link to a translated page ( [[xx:abc]] ). So this shouldn’t be a big problem. A few days ago I’ve translated the Infobox_small template like that and I’ve also added a redirection (DE:Template:Infobox_small to Template:DE:Infobox_small) because I thought it would be better to have all templates in the same namespace.
Bye, Andreas