Menu items are not localized

You are right about that. And yes, its a bug.
As I actually prefer that neither menu item nor tooltip are localized, I will make it customizable whether the toolbar is localized or not. Defaulting it to being localized.

My proposal will have to wait as it wasn't as straightforward as I imagined. I will just fix the bug now.

The bug: that menu items aren't localized
My proposed feature: to be able to force a language

I have created a new issue for the proposed feature (http://drupal.org/node/1770296)

Fixed and released as 7.x-1.1

In 7.x-1.1 the menu items are not translated for me.

I use i18n_menu to translate my items with this option checked in my "edit menu" tab :
Translate and Localize. Menu items with language will allow translations. Menu items without language will be localized.

A solution is to use i18n_menu_localize_tree() in webmaster_menu_get_tree :

function webmaster_menu_get_tree($menu_name) {
  $tree = menu_tree_all_data($menu_name);

  // Allow i18n module to translate strings where available.
  if (module_exists('i18n_menu')) {
    $tree = i18n_menu_localize_tree($tree);
  }

  $menu_items = webmaster_menu_create_datastructure_from_tree($tree);
  return $menu_items;
}

Here's a patch for #5

Sorry for this very late reaction. I have tested the patch, and it works fine. I will commit soon.

Sorry for this very late reaction. I have tested the patch, and it works fine. Thank you, nikosnikos. I will commit soon.

The patch has now been committed. I expect to roll a new release in about a week, after going through the rest of the issues that have accumulated