Change permalink structure in all sites of a multisite

You would probably need to do this programmatically, for example add a PHP file to your /wp-content/mu-plugins/ folder with this:

<?php
add_action('init', 'modify_all_permalink_structures');
function modify_all_permalink_structures();
        if (isset($_GET['modify_all_permalinks')) {
            $structure="/%category%/%postname%/";
            $sites = get_sites();
            foreach ( $sites as $site ) {
                switch_to_blog( $site->blog_id );
                global $wp_rewrite;
                $wp_rewrite->set_permalink_structure($structure);
                $wp_rewrite->flush_rules();
            }
            restore_current_blog();
       }
}

Then access yoursite.com/?modify_all_permalinks to trigger it.

Recommend you do a full site backup first in case this is somehow insufficient. Remove the file when it has done it’s job.