Different coloured navigation links in Twenty Eleven themes

You can add custom html classes to each menu item and then use those classes to add the bottom border.

In the Admin Dashboard, under Appearance, click on Menus.

Select your menu and click the small down arrow to the right of the menu item box.

If the CSS Classes box is missing, Click the Screen Options tab at the top of the page and check the CSS Classes option.

In the CSS Classes box add the class for the color of the bottom border you want to used. For example nav-yellow, nav-green, etc.

In your style sheet, add the corresponding class styles:

.nav-yellow {
}

.nav-green {
}