There are numerous theories about this.
- The theories restricted to Japanese origins all revolve around the ideas of some larger geographic area that was split into "upper" (-kami or -gami) and "lower" (-shimo) halves. The main theories listed at the JA Wikipedia article on 武蔵国 (Musashi no Kuni) and at the Nihon Jiten page here revolve around an ancient province named Musa or Munza (or possibly even Fusa). After the ostensible split, there would have been Musa-gami and Musa-shimo, and the theory goes that the name Musa-gami lost the leading mu to become Sagami, while Musa-shimo lost the trailing mo to become Musashi.
→ This seems a little strained and unlikely, however.
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.
- Per Vovin's paper mentioned in the EN Wikipedia article: Japanese musashi, from older muzashi, from yet older munzashi, from Ainu mun ("grass, weeds") sa ("open, exposed; a plain, a wide-open area") -hi (third-person possessive suffix), with Ainu hi becoming Japanese shi (as observed in other likely terms). So mun sa-hi would ostensibly mean "grassy or weedy plain".
→ This holds together reasonably well. However, I cannot find any mention of this -hi possessive suffix in Batchelor's seminal Ainu dictionary. I do find another -hi, used as a nominalizing suffix for verbs and adjectives. I also see mention of -i, again used as a nominalizing suffix for verbs and adjectives. This is also used to indicate demonstrative pronouns, and to indicate direction to or from a place.
I find this gap in Vovin's etymology rather odd, especially as the paper explicitly cites Batchelor's dictionary as the source for the Ainu word sa, and as Batchelor's work also lists Ainu mun as "grass, weeds" in agreement with Vovin's etymology.
- Per the Nihon Jiten entry, Japanese musashi, then probably from much older possible mushashi (see Spelling below), from Ainu mo ("sluggish, quiet, gentle") casi ("fort, castle; enclosure", where Ainu ca is read similarly to Japanese ちゃ).
→ This doesn't seem very likely.
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.