There is no magic plugin or SQL query that will do this for you.
Why It’s Broken and Not in The Way You Thought
There is only one taxonomy, because of this:
'taxonomies' => array( 'category' ),
While your sites code may have registered multiple custom taxonomies perhaps even with different names, URLs, and semantics, because they all use the name category the database does not distinguish between them, and they are the same taxonomy.
Editing A in the first one doesn’t also edit A in the second one, they are literally the same term and there is no distinction, there is only 1 entry in the database, not 2.
Because there is only 1 term, not 2, there is nothing to rename to fix this.
Note that sometimes using a single taxonomy across multiple post types is desirable and useful.
Fixing This
This will be painful and time consuming to fix, as it has to be done almost entirely by hand.
You need to create new taxonomies with unique names that do not match, adjust all your post type registrations to use those instead, then create new terms and assign them to your posts. Taxonomies is the easiest part as you would need to prefix the taxonomy slug/name to fix the problem for future terms, and use the new name in the CPT registration. Migrating content is the difficult part
This will be very heavy on manual work, and there is little that can be done to avoid it. The best you can hope for is being able to duplicate the terms in another taxonomy to save time on recreating them, but the bulk of the work is in re-assigning posts, and if you do it on a per post basis the term recreation is done as you’re entering terms.