simbaclaws on "Change product-category slug into store slug"

So basically I have a url structure that should be like this:
http://mydomain.com/store/main-category/sub-category

But what happens is that whenever I navigate from: http://mydomain.com/store to a category it changes the url to this:
http://mydomain.com/product-category/main-category/sub-category

I would like to change this "product-category" to be the store slug instead of a product-category slug.

I've looked on this forum and other forums for a solution and found this thread: https://wordpress.org/support/topic/plugin-woocommerce-excelling-ecommerce-remove-product-category-and-product-slugs-from-the-url?replies=7

Now my main issue with this thread is that I'm not using SEO Ultimate but Yoast SEO and I did find an option in Yoast SEO that tells me to remove "category" from the url structure, but this doesn't remove the "product-category" from the url structure. Not only that, I want to change this structure's slug name, not remove it.

Does anyone have an idea on how I could accomplish this?

EDIT: I found out it is possible to change this in settings -> permalinks. But whenever I set it up to be the store slug, I get 404 pages when trying to connect to categories. Would I have to recreate all category's?