Set base 'shop' URL to something else in Commerce
The way the demo templates are set up they are a series of included sub-templates.
So you would need to change the references to shop/ for each of the {% include %} statements.

Try doing a find/replace on the templates within your /store directory. See what that does.

Craft/Commerce places no restriction on how you name things. You don't need to use the demo templates at all if you don't want to. You can name them and place them wherever you like.