checkbox in post add/edit to add/remove the post from menu

The following is just a proof of concept and needs to be adapted/improved to work per the Question requirements.

It creates a meta box with a dropdown listing all available Navigation Menus. On post save, it is added to the selected menu.

This Q&A was used as starting point: Programmatically add a Navigation menu and menu items. The relevant functions are wp_get_nav_menus and wp_update_nav_menu_item. I’m not sure how to remove a menu item, but probably wp_delete_post must be used.

add_action( 'add_meta_boxes', 'add_custom_box_wpse_87594' );
add_action( 'save_post', 'save_postdata_wpse_87594', 10, 2 );

function add_custom_box_wpse_87594() 
{
    add_meta_box( 
        'section_id_wpse_87594',
        __( 'Available Nav-Menus' ),
        'inner_custom_box_wpse_87594',
        'post',
        'side'
    );
}

function inner_custom_box_wpse_87594() 
{
    $navmenus = wp_get_nav_menus( array( 'hide_empty' => false, 'orderby' => 'none' ) );

    // DEBUG
    // echo '<pre>' . print_r( $navmenus, true ) . '</pre>';

    wp_nonce_field( plugin_basename( __FILE__ ), 'noncename_wpse_87594' );

    echo '<select name="nav_menus_dropdown" id="nav_menus_dropdown">
        <option value="">- Select -</option>';

    foreach( $navmenus as $m ) 
    {
        printf( 
            '<option value="%s">%s</option>',
            $m->term_id,
            $m->name
        );
    }

    echo '</select>';   
}

function save_postdata_wpse_87594( $post_id, $post_object ) 
{
    // Auto save?
    if ( defined( 'DOING_AUTOSAVE' ) && DOING_AUTOSAVE )  
        return;

    // Security
    if ( 
        !isset( $_POST['noncename_wpse_87594'] ) 
        || !wp_verify_nonce( $_POST['noncename_wpse_87594'], plugin_basename( __FILE__ ) ) 
        )
        return;

    // Correct post_type
    if ( 'post' != $post_object->post_type )
        return;

    if( !empty( $_POST['nav_menus_dropdown'] ) )
    {
        wp_update_nav_menu_item(
            $_POST['nav_menus_dropdown'], 
            0, 
            array(
                'menu-item-title' => $_POST['post_title'],
                'menu-item-object' => 'page',
                'menu-item-object-id' => $_POST['ID'],
                'menu-item-type' => 'post_type',
                'menu-item-status' => 'publish'
            )
        );
    }       
}

Result: