Comment 4 for bug 772952

Digging a bit more... Seems not that easy. First, we'd need a specific name for the link and this alone defeats the purpose because the only thing we want translated here is the link description.

I wonder whether that would help:
http://bloggingsquared.com/web-development/widget-to-translate-blog-link-categories-with-wpml/