This registers a custom meta box for nav menus and renders it. Obviously $my_items would ideally be not hard-coded and instead it would come somewhere from the DB. The custom items add to the menu and save properly, but will probably not be displayed correctly. You might need to hook to the 'wp_setup_nav_menu_item' filter in order to fix the men…

custom-menu-panel.php

<?php

function my_register_menu_metabox() {
	$custom_param = array( 0 => 'This param will be passed to my_render_menu_metabox' );
	
	add_meta_box( 'my-menu-test-metabox', 'Test Menu Metabox', 'my_render_menu_metabox', 'nav-menus', 'side', 'default', $custom_param );
}
add_action( 'admin_head-nav-menus.php', 'my_register_menu_metabox' );

/**
 * Displays a menu metabox 
 *
 * @param string $object Not used.
 * @param array $args Parameters and arguments. If you passed custom params to add_meta_box(), 
 * they will be in $args['args']
 */
function my_render_menu_metabox( $object, $args ) {
	global $nav_menu_selected_id;

	// Create an array of objects that imitate Post objects
	$my_items = array(
		(object) array(
			'ID' => 1,
			'db_id' => 0,
			'menu_item_parent' => 0,
			'object_id' => 1,
			'post_parent' => 0,
			'type' => 'my-custom-type',
			'object' => 'my-object-slug',
			'type_label' => 'My Cool Plugin',
			'title' => 'Custom Link 1',
			'url' => home_url( '/custom-link-1/' ),
			'target' => '',
			'attr_title' => '',
			'description' => '',
			'classes' => array(),
			'xfn' => '',
		),
		(object) array(
			'ID' => 2,
			'db_id' => 0,
			'menu_item_parent' => 0,
			'object_id' => 2,
			'post_parent' => 0,
			'type' => 'my-custom-type',
			'object' => 'my-object-slug',
			'type_label' => 'My Cool Plugin',
			'title' => 'Custom Link 2',
			'url' => home_url( '/custom-link-2/' ),
			'target' => '',
			'attr_title' => '',
			'description' => '',
			'classes' => array(),
			'xfn' => '',
		),
		(object) array(
			'ID' => 3,
			'db_id' => 0,
			'menu_item_parent' => 0,
			'object_id' => 3,
			'post_parent' => 0,
			'type' => 'my-custom-type',
			'object' => 'my-object-slug',
			'type_label' => 'My Cool Plugin',
			'title' => 'Custom Link 3',
			'url' => home_url( '/custom-link-3/' ),
			'target' => '',
			'attr_title' => '',
			'description' => '',
			'classes' => array(),
			'xfn' => '',
		),
	);
	$db_fields = false;
	// If your links will be hieararchical, adjust the $db_fields array bellow
	if ( false ) {
		$db_fields = array( 'parent' => 'parent', 'id' => 'post_parent' );
	}
	$walker = new Walker_Nav_Menu_Checklist( $db_fields );

	$removed_args = array(
		'action',
		'customlink-tab',
		'edit-menu-item',
		'menu-item',
		'page-tab',
		'_wpnonce',
	); ?>
	<div id="my-plugin-div">
		<div id="tabs-panel-my-plugin-all" class="tabs-panel tabs-panel-active">
		<ul id="my-plugin-checklist-pop" class="categorychecklist form-no-clear" >
			<?php echo walk_nav_menu_tree( array_map( 'wp_setup_nav_menu_item', $my_items ), 0, (object) array( 'walker' => $walker ) ); ?>
		</ul>

		<p class="button-controls">
			<span class="list-controls">
				<a href="<?php
					echo esc_url(add_query_arg(
						array(
							'my-plugin-all' => 'all',
							'selectall' => 1,
						),
						remove_query_arg( $removed_args )
					));
				?>#my-menu-test-metabox" class="select-all"><?php _e( 'Select All' ); ?></a>
			</span>

			<span class="add-to-menu">
				<input type="submit"<?php wp_nav_menu_disabled_check( $nav_menu_selected_id ); ?> class="button-secondary submit-add-to-menu right" value="<?php esc_attr_e( 'Add to Menu' ); ?>" name="add-my-plugin-menu-item" id="submit-my-plugin-div" />
				<span class="spinner"></span>
			</span>
		</p>
	</div>
	<?php
}

Hii.. sorry this not work for me... im using WP 4.5.2
im try to copy and paste your code but still not work... please help me

sorry my english is bad..

Its metabox is not showing in customizer.

how to work in customizer

Thank you !

Love the approach. However, the url field is not being passed / saved. Any ideas?

Following up; setting the 'type' to 'custom' will render the url field.

Cheers!

thanks @sododesign @greabs

@greabs change 'type' => 'my-custom-type', for 'type' => 'custom',

I am stuck at how to make the child pages appear in a hierarchy format in my custom post type. Any thoughts?