I've been all over acp and cant figure out how to do it, the obvious place would be in the menu editor but it doesn't seem possible

I've got commerce installed but only ever intend to use it to sell premium membership and I'd like to be able to change the menu from "Store" to " Subscribe"

If the name can’t be changed in the menu manager, it’s a language string. So you change it in the language section of the ACP. You can also use the translation tools there to quickly find the string. 

You have a couple of different ways to go about what you want.  

1. If you want to change the entire name of the Store, you can change the language string. 

2. You can use the menu manager to link to anything you want, like a product or your own custom page.