Add rel="nofollow" to menu displayed by menu_block module
If you use different menus then:

There's a module for that(tm) Menu Attributes

If it's the same menu then things get farm more complicated as you'll have to implement some hook. Take a look at hook_menu_block_tree_alter in menu_block.api.php.