Read the script comments bellow 😉

/**
* Automatically updates the WooCommerce "Categories" menu by adding product categories
* and their hierarchical structure. It excludes the "Uncategorized" category.
*
* How it works:
* 1. Fetches the WooCommerce menu with the name "Categories".
* 2. Iterates through all product categories in the taxonomy 'product_cat'.
* 3. Adds top-level categories to the menu if they do not already exist.
* 4. Recursively adds child categories under their respective parent categories.
* 5. Skips the "Uncategorized" category to avoid clutter in the menu.
* 
* Hooks:
* - Runs on `create_product_cat` and `edited_product_cat` actions to ensure the menu stays updated.
*
* Usage:
* - Ensure the menu named "Categories" exists in your WordPress site.
* - Ensure you have already add manually the first level parent "Categories" (if not, it still works)
* - Categories will be dynamically added, preserving parent-child relationships.
* - Existing menu items are reused to prevent duplication.
*
* Credits:
* - Developed by Nicolas Lagios
* - Website: https://nicolaslagios.com
* - Donations: https://paypal.me/nicolaslagios
*/

function update_woocommerce_categories_menu() {
    $menu_name = 'Categories';
    $menu_exists = wp_get_nav_menu_object($menu_name);
    if (!$menu_exists) {
        return; // Exit if the menu does not exist.
    }

    $menu_id = $menu_exists->term_id;

    // Fetch all product categories
    $product_categories = get_terms(array(
        'taxonomy' => 'product_cat',
        'hide_empty' => false,
        'orderby' => 'name',
        'order' => 'ASC'
    ));

    // Helper function to find a menu item by term ID
    function find_menu_item_id_by_category($category, $menu_id) {
        $menu_items = wp_get_nav_menu_items($menu_id);
        if ($menu_items) {
            foreach ($menu_items as $menu_item) {
                if ($menu_item->object_id == $category->term_id && $menu_item->object == 'product_cat') {
                    return $menu_item->ID; // Return the menu item ID
                }
            }
        }
        return 0; // Return 0 if not found
    }

    // Recursive function to add categories
    function add_category_to_menu($category, $menu_id, $parent_id = 0) {
        // Skip the "Uncategorized" category
        if ($category->slug === 'uncategorized') {
            return;
        }

        // Check if this category is already in the menu
        $existing_menu_item_id = find_menu_item_id_by_category($category, $menu_id);
        if (!$existing_menu_item_id) {
            // Add category to the menu
            $menu_item_id = wp_update_nav_menu_item($menu_id, 0, array(
                'menu-item-title' => $category->name,
                'menu-item-url' => get_term_link($category),
                'menu-item-status' => 'publish',
                'menu-item-type' => 'taxonomy',
                'menu-item-object' => 'product_cat',
                'menu-item-object-id' => $category->term_id,
                'menu-item-parent-id' => $parent_id
            ));
        } else {
            $menu_item_id = $existing_menu_item_id; // Use existing menu item ID
        }

        // Get child categories
        $children = get_terms(array(
            'taxonomy' => 'product_cat',
            'hide_empty' => false,
            'parent' => $category->term_id
        ));
        foreach ($children as $child) {
            add_category_to_menu($child, $menu_id, $menu_item_id); // Recursively add children
        }
    }

    // Add top-level categories and their children
    foreach ($product_categories as $category) {
        if ($category->parent == 0 && $category->slug !== 'uncategorized') { // Top-level category and not "Uncategorized"
            add_category_to_menu($category, $menu_id);
        }
    }
}

// Run the function when product categories are created or updated
add_action('create_product_cat', 'update_woocommerce_categories_menu');
add_action('edited_product_cat', 'update_woocommerce_categories_menu');