What is the etymology of the old province and Japanese name 武蔵?
Wikipedia claims that it is non-Yamato vocabulary from an Ainu language. Even if this is true, why were these characters (military/weapon + store) chosen as ateji?
There are numerous theories about this.
Other theories look beyond just Japanese for the origins of the name, and find possibilities in Ainu, as mentioned in the EN Wikipedia article, and maybe even Korean, as mentioned in the Nihon Jiten entry.
We don't know where musashi really comes from, or what it might have originally meant. All the theories I've read so far have holes in them, and none seem conclusive. From my personal perspective, Vovin's Ainu derivation seems the closest to convincing, but that hypothesized final -hi remains unexplained.
From the JA Wikipedia article, specifically the section at https://ja.wikipedia.org/wiki/%E6%AD%A6%E8%94%B5%E5%9B%BD#.E5.9B.BD.E5.90.8D (my additions in [square brackets]):
For the spelling, we find 无耶志国 [probably mu ya shi kuni, maybe mu sha shi kuni] in the Asuka wooden fragments [see this EN Wikipedia article for more], and there are also records that show spellings of 无射志 (muzashi) and 牟射志 (munzashi) until around the 7th century. Additional spellings include 牟佐志 and 無邪志, but all of these are thought to be reading-based ateji.
As for your specific question, "why were these characters (military/weapon + store) chosen as ateji", I have not yet found any sources stating specific reasons, though presumably the use of 武 had something to do with the military importance of the area.