Perhaps I misunderstand the issue.
mysite.com/category/shoes/ can easily be changed to mysite.com/store/shoes/
It is really easy to change that prefix to anything you like.
Go in your WP-Admin Panel and go to Settings » Permalinks
There you will see an Optional box which allows you to change the category base prefix and the tag base prefix. Then Save Changes
This is explained in detail here:
http://www.wpbeginner.com/wp-tutorials/how-to-change-the-category-base-prefix-in-wordpress/
