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();