By default, WordPress menus don’t have the ability to add “nofollow” to the link items…but WordPress 3.0+ has the functionality built in.
This tutorial will show you how to add nofollow to specific items using the new wp_nav_menu() function.
Enable nofollow in WordPress 3.0 nav menus
1. Click the “Screen Options” tab

2. Check the “Link Relationship (XFN) box

Notice all the other options for menu items (posts, tags aren’t enabled by default) and menu item properties (link targets, classes, descriptions).
3. Enter “nofollow” as the Link Relationship (XFN)

There’s an alternative way to do this as well.
You can add this to the functions.php
Using the code below, you can automate this whole process, which would be nice if you want to do this all at once.
You can also specify only to add nofollow to only one menu location or one menu.
add_filter('walker_nav_menu_start_el', 'nofollow_menu_items', 1, 4);
function nofollow_menu_items($item_output, $item, $depth, $args) {
$nofollow = array(105,268); // Menu item id's (View page source and menu-item-123)
$location = ''; // Use 'primary' to only filter header menu in twentyten
$menu = ''; // Use menu names to filter by menu
if(
in_array($item->ID, $nofollow)
&& (!empty($location) && $args->theme_location == $location || empty($location))
&& (!empty($menu) && $args->menu == $menu || empty($menu))
) {
$item_output = str_replace('<a ', '<a rel="nofollow" ', $item_output);
}
return $item_output;
}
