How to make a plugin auto-add item to nav menu

this is the general gist of what you need to do, you’ll want to add some checks in here, make sure you get a valid menu returned, etc..

$locations = get_theme_mod( 'nav_menu_locations' );
$menu = wp_get_nav_menu_object( reset( $locations ) ); // get first item in menu locations array
$menu_item_data = array(
    'menu-item-object-id' => $your_page->ID, // ID of the page you want to add
    'menu-item-parent-id' => 0,              // top level menu item
    'menu-item-position' => 0,               // setting position to 0 will add it to the end
    'menu-item-object' => 'page',
    'menu-item-type' => 'post_type',
    'menu-item-status' => 'publish'
);
wp_update_nav_menu_item( $menu->term_id, 0, $menu_item_data );