How to get a custom post type archive paged when using a custom field for post sorting?

You shouldn’t be using a custom query for a post type archive page. Pagination being difficult is one of the reasons. If you want to change your post type archive to sort by a custom field, hook into pre_get_posts to modify the main query:

function wpse_282839_post_type_order( $query ) {
    if ( ! is_admin() && $query->is_post_type_archive( 'restaurante' ) ) {
        $query->set( 'posts_per_page', 4 );
        $query->set( 'meta_key', 'destacado' );
        $query->set( 'orderby', 'meta_value' );
        $query->set( 'order', 'DESC' );
    }
}
add_action( 'pre_get_posts', 'wpse_282839_post_type_order' );

Then just use the normal loop and pagination links in your archive template.