Add class-element to a link though a module (or can I implement theme_link in a module instead of in a theme)?
What I understand is that you want to have a class in every link that comes on the site.
I believe, you can achieve this by skinr module - https://drupal.org/project/skinr, which not only adds up classes but also provides you UI to achieve the same.

Also, in module, you can try this.

/**
 * Implements hook_preprocess_HOOK
 */
function MODULENAME_preprocess_menu_link (&amp;$variables) {
  if ($variables['element']['#original_link']['menu_name'] == 'main-menu') {
    $variables['element']['#title'] = '&lt;i class="icon-' . _sanitize_words($variables['element']['#title']) . '"&gt;&lt;/i&gt;' . $variables['element']['#title'];
  }
}


The above could should work, Worked for me atleast :)