I would say you already have the answer. The thing I would recommend is to create a CPT called Store. That will give you the capability of having something like:
example.com/store/store-name
Being store the name of your CPT.
Now with the taxonomy:
First approach: Just one taxonomy
Now, you would create a custom taxonomy for the CPT, maybe called store_category and have the states, cities and store numbers being created as terms under this category, hierarchically.
The problem with this approach is that creating the permalink structure will be difficult since there is no way to specify a top level or second level term inside the permalink. So I would opt for the second approach.
Second Approach: multiple Taxonomies
I would create one taxonomy called state, one called city and one called store_number. This may seem overhead but this will give you a logic separation between one type of taxonomy and the other. Once this is ready, now you would only need to hack the permalinks for this CPT to get the url structure you are looking for.
In general, you now should have the capability to define a permalink structure like:
example.com/%state%/%city%/%store_number%/%post_name%
This could be achieve with a plugin like Custom Post Type Permalinks Custom Post Type Permalinks
I think this is the best way to get this relationship going.