Wordpress - How to add custom post type archive page links to nav menu?

As of WordPress 4.4 (December 2015), Custom Post Type archive links are now officially supported in WordPress core without any third-party code or plugins needed.

You can read the entire Trac #16075 ticket for a full discussion or the Make WordPress Core post for a summary of the additional labels.

To enable the new built-in support for archive menu links, custom post types have to registered with non-falsey (i.e. true) values for has_archive, publicly_queryable and show_in_nav_menus:

add_action( 'init', function () {
    register_post_type( 'movies',
        array(
            'labels' => array(
                'name' => __( 'Movies' ),
                'singular_name' => __( 'Movie' ),
                'archives' => __( 'Movies' ),
            ),
            'public' => true,
            'has_archive' => true,
            'rewrite' => array(
                'slug' => 'movies',
            ),
        )
    );
});

With these additions, you'll see a new metabox on the Appearance > Menus admin screen.

The post type archive link can be found under the 'View All' tab within the post type metabox:

Note: You may need to toggle the "screen options" drawer and ensure that your "Post Type Archives" name (e.g. Movies) is checked in order for it appear on the Menus screen.