How do I make angular.js reevaluate / recompile inner html?

You have to $compile your inner html like

.directive('autotranslate', function($interpolate, $compile) {
    return function(scope, element, attr) {
      var html = element.html();
      debugger;
      html = html.replace(/\[\[(\w+)\]\]/g, function(_, text) {
        return '<span translate="' + text + '"></span>';
      });
      element.html(html);
      $compile(element.contents())(scope); //<---- recompilation 
    }
  })