Create multidimensional array of taxonomies

The following should work, if I understand what you want correctly.

Basically the only change is where you display the list items – instead of echoing it, you save it to the array. We also know the store type at that point, so we can save them both in their own array as a new element in the main array.

$all_store_info = array(); // Declare array to save the store info

$post_type="store";
$tax = 'store_type';

$tax_terms = get_terms('store_type');
if ( $tax_terms ) {
    foreach ($tax_terms as $tax_term) {

        $args = array([...]); // trimmed to make it easier to see changes
        $my_query = new WP_Query($args);

        if ( $my_query->have_posts() ) : 
            while ($my_query->have_posts()) : $my_query->the_post(); 

                $type_terms = wp_get_post_terms( $post->ID, 'state');
                if ( $type_terms ) {

                    /* Add this store type from $tax_term from the outer loop
                       and the first (presumably only) state to our array */
                    $all_store_info[] = array( 
                                            "store_type" = $tax_term->name,
                                            "state"      = $type_terms[0]->name
                                        );
                }

            endwhile; 
        endif;
    }
}
wp_reset_postdata();