Add category label for appearance > menus items

There are not good/easy hooks to achieve this, but I think this is possible, just needs some work. I can give you general direction and some ideas.

You can use hooks on nav_menu_items_page and nav_menu_items_page_recent to return array of posts with changed title. They both may use the same function, like this

function my_nav_menu_items($posts, $args) {
    foreach ($posts as $post) {
        // get category name or whatever you need for title
        $post->post_title = $post->post_title . " [..CATEGORY..]";
    }
    return $posts;
}
add_filter('nav_menu_items_page', 'my_nav_menu_items', 10, 2);
add_filter('nav_menu_items_page_recent', 'my_nav_menu_items', 10, 2);

But now you have another problem, your updated title will be used as menu link title when you save your menus. To prevent this you may try to add additional hook on wp_insert_post_data or something like that, check for post_type being nav_menu_item and then remove your added category from title value. You some square brackets or distinctive separator to make this easier.