Assign a different menu depending on custom taxonomy

I think the way to do this is:

  1. Set up your menu in Appearance > Menus as you mentioned;
  2. In your theme’s header.php (or wherever you find the wp_nav_menu() code that displays your current menu), set up a WordPress conditional to check if the page being visited is a location taxonomy archive, and display different menus based on that. For instance:

    if (is_tax('location')) {
    wp_nav_menu( array($args = array(
    'menu' => 'test-menu', // your menu slug here
    )
    );
    } else {
    wp_nav_menu(); // your original menu code here
    }

See the Conditionals page in the WordPress codex for all the options you could use here, there are many.