When you register a custom post type, set the argument show_in_nav_menus to TRUE, and WordPress will create the box for you automatically. This works for custom taxonomies too.
Example, requires PHP 5.4 or newer.
add_action( 'wp_loaded', function() {
$post_type="foo";
add_action( 'registered_post_type', function( $registered ) use ( $post_type ) {
if ( $registered !== $post_type )
return;
register_taxonomy(
'bar',
$post_type,
[
'label' => 'Bars',
'public' => TRUE,
'show_in_nav_menus' => TRUE
]
);
});
register_post_type(
$post_type,
[
'label' => 'Foo',
'public' => TRUE,
'show_in_nav_menus' => TRUE
]
);
});
Adding a custom box for anything else is more difficult. Well, adding it is easy, it is just a metabox with the parameter $screen set to nav-menus:
add_action( 'admin_init', function() {
add_meta_box(
'test',
'Custom Box',
function() {
print 'Insert content here.';
},
'nav-menus',
'side',
'low'
);
});
The difficult part are the following actions: creating the proper HTML for the list items, saving those items with AJAX requests and rendering them in a nav menu on front-end. Inspect the built-in boxes for the details. Repeating and explaining that would require a novel.
The out put of both code examples should look like this:
You can see the boxes for the post type Foo, the taxonomy Bars and the Custom Box. Form is one of my own post types on that installation, Location on of my taxonomies, and Languages a custom box for all available languages in a multilingual network built with Multilingual Press.