Worked it out.
Assuming using a theme which has a menu location called ‘primary’, and you have just created a menu with an id contained in $menu_id
$menu_locations = get_nav_menu_locations();
$new_menu_locations = array_map( 'absint', ['primary' => $menu_id]);
$menu_locations = array_merge( $menu_locations, $new_menu_locations );
set_theme_mod( 'nav_menu_locations', $menu_locations );
This is pretty much exactly how WordPress itself saves updated menu locations in wp-admin/nav-menus.php