Updating posts exceeds maximum execution time

You do have a large amount of posts which will crash your server (due to maximum execution time being exceeded) with such an expensive operation. We will need to run this in a much more cleverer way.

First of all, we would want to get all posts, except revision and nav_menu_item. Revision post_names are build in a different way, and trying to handle them with other post types will indeed also crash your server

Secondly, we need to run a filter on WP_Query in order that we only get the ID, post_name, post_title, post_status, post_type and post_parent fields of the post. This will greatly ease the strain on your server

Thirdly, we need to ignore updating all term and post meta caches. This also adds extra unnecessary strain on your resources, so we need to exclude updating them because, frankly, we do not need post terms and meta

ALL POST TYPES EXCEPT REVISIONS

With such a large amount of posts, you would probably need to run it a few times, but with a huge improvement from the code you are using, you might probably get away with running it once

You can try the following: (You can drop this into functions.php or replace your existing code in the plugin with my code)

add_action( 'wp', function ()
{
    global $wpdb;

    add_filter( 'posts_fields', function ( $fields, \WP_Query $q ) use ( $wpdb )
    {
        remove_filter( current_filter(), __FUNCTION__ );

        // Only target a query where the new custom_query parameter is set with a value of custom_meta_1
        if ( 'custom_meta_1' === $q->get( 'custom_query' ) ) {
            // Only get the ID, post_name, post_title, post_status, post_type and post_parent fields to reduce server load
            $fields = "
                $wpdb->posts.ID,
                $wpdb->posts.post_title,
                $wpdb->posts.post_name,
                $wpdb->posts.post_type,
                $wpdb->posts.post_status,
                $wpdb->posts.post_parent
            ";
        }

        return $fields;
    }, 10, 2);

    // Get all public post types
    $post_types = get_post_types( ['public' => true] );

    $args = [
        'post_type'              => $post_types,
        'posts_per_page'         => -1,              
        'suppress_filters'       => false,           // Allow the posts_fields filter
        'custom_query'           => 'custom_meta_1', // New parameter to allow that our filter only target this query
        'update_post_term_cache' => false,
        'update_post_meta_cache' => false
    ];
    $q = get_posts( $args );

    // Make sure we have posts before we continue, if not, bail
    if ( $q ) {

        // Loop through the posts
        foreach ( $q as $single_post ) {
            // Sanitize our post title
            $new_slug = sanitize_title( $single_post->post_title );

            // Check if our $new_slug is not equal to our post_name
            if ( $single_post->post_name === $new_slug )
                continue; // Do nothing further

            // Our new slug and post name does not match, lets save a unique post_name
            $post_name = wp_unique_post_slug( 
                $new_slug, 
                $single_post->ID,
                $single_post->post_status, 
                $single_post->post_type, 
                $single_post->post_parent       
            );

            // Last change to bail before we update the post_name field
            if ( false !== stripos( $single_post->post_name, $post_name ) )
                continue;

            //Update the post_name field, wpdb::update is the quickest
            $wpdb->update(   
                'wp_posts', 
                ['post_name' => $post_name],    // string
                ['ID'        => $single_post->ID], 
                '%s',
                '%s' 
            );  
        } // endforeach $q
    }
}, PHP_INT_MAX );

EDIT – REVISIONS

The code above, as stated, should be used for all posts except revisions as revision’s post_name is build differently.

The code below will update the post_name field for revisions. You should not run this code together with the code above, it will definitely break your servers’ back with the amount of posts you have. You should run code block one, remove it and then run code block two, and remove it once done, specially code block two as it is really expensive.

Here is the code:

add_action( 'wp', function ()
{
    global $wpdb;

    add_filter( 'posts_fields', function ( $fields, \WP_Query $q ) use ( $wpdb )
    {
        remove_filter( current_filter(), __FUNCTION__ );

        // Only target a query where the new custom_query parameter is set with a value of custom_meta_1
        if ( 'custom_meta_1' === $q->get( 'custom_query' ) ) {
            // Only get the ID, post_name, post_title, post_status, post_type and post_parent fields to reduce server load
            $fields = "
                $wpdb->posts.ID,
                $wpdb->posts.post_title,
                $wpdb->posts.post_name,
                $wpdb->posts.post_type,
                $wpdb->posts.post_status,
                $wpdb->posts.post_parent
            ";
        }

        return $fields;
    }, 10, 2);

    $args = [
        'post_type'              => 'any',
        'post_status'            => 'any',
        'posts_per_page'         => -1,
        'custom_query'           => 'custom_meta_1', // New parameter to allow that our filter only target this query
        'update_post_term_cache' => false,
        'update_post_meta_cache' => false
    ];
    $q = get_posts( $args );

    // Make sure we have posts before we continue, if not, bail
    if ( $q ) {
        // Now we can get the post revions and loop throught them
        foreach ( $q as $single_post ) {
            $rev_args = [
                'post_type'              => 'revision',
                'post_status'            => 'inherit',
                'post_parent'            => $single_post->ID,
                'posts_per_page'         => -1,
                'order'                  => 'ASC',
                'custom_query'           => 'custom_meta_1', // New parameter to allow that our filter only target this query
                'update_post_term_cache' => false,
                'update_post_meta_cache' => false
            ];
            $revisions = get_posts( $rev_args );

            // Make sure we have revions before we continue
            if ( $revisions ) {
                // Loop through the revisions and set post_name
                foreach ( $revisions as $key=>$revisions ) {
                    // Build a revision post slug in the format {$post->post_parent}-revision-v{$key + 1}
                    $post_name = $single_post->ID . '-revision-v' . ( $key + 1 );

                    // Make sure that we don't have a post_name yet with the name $post_name
                    if ( $revisions->post_name === $post_name )
                        continue; // Do nothing

                    //Update the post_name field, wpdb::update is the quickest
                    $wpdb->update(   
                        'wp_posts', 
                        ['post_name' => $post_name],    // string
                        ['ID'        => $revisions->ID], 
                        '%s',
                        '%s' 
                    );  
                }
            }
        }
    }
}, PHP_INT_MAX );

EDIT – Between 2015-07-08 23:23:45 and 2016-02-21 09:42:31

If you only need to target posts and revisions between the two specific dates, you can add the following inside your query args in $args in both blocks of code with a date_query

'date_query' => [
    [
        'after'     => '2015-07-08 23:23:45',
        'before'    => '2016-02-21 09:42:31',
    ],
],

So

$args = [
    'post_type'              => $post_types,
    'posts_per_page'         => -1,              
    'suppress_filters'       => false,           // Allow the posts_fields filter
    'custom_query'           => 'custom_meta_1', // New parameter to allow that our filter only target this query
    'update_post_term_cache' => false,
    'update_post_meta_cache' => false
];

in block one becomes

$args = [
    'post_type'              => $post_types,
    'posts_per_page'         => -1,              
    'suppress_filters'       => false,           // Allow the posts_fields filter
    'custom_query'           => 'custom_meta_1', // New parameter to allow that our filter only target this query
    'update_post_term_cache' => false,
    'update_post_meta_cache' => false,
    'date_query'             => [
        [
            'after'          => '2015-07-08 23:23:45',
            'before'         => '2016-02-21 09:42:31',
        ],
    ],
];