For some reason my apps and store is on my local language while windows itself is on English. How can I change everything to be on English?
Go to Control Panel > Clock, Language and Region > Language and either remove the unnecessary language OR if you need to keep the language for some reason (e.g. keyboard input in your local language), move it below English using the "Move down" button (shown below). The store uses the language that's at the top of the list.
Alternatively, open the Settings app, go to the Time & language category, then click the Region & language sidebar item. Here you'll se a list of installed languages. Click the language you want to use and press Set as default
The above answers were probably correct, however languages have now, in June 2020, been migrated to Settings from Control Panel. (The confusion between settings and control panel drives me mad. Why not just have one or the other, but not both!?)
So the answer should now be
Press Windows key -> Search for "Settings" -> Search for "Language" in settings Change order of languages, bringing your preferred language to the top.
In my case, the Microsoft Store App started appearing in English when I moved English above Italian (I'm English but live in Italy), as below