After getting STORE, my grid looked like this:

STORE
***** (ADO)
***** (DIU)
****E (AS)
***E* (R)

Not much to go by, but I noticed the last word didn't have any more of the 5 main vowels. That's something! I quickly ruled out that the first three letters were consonants (if there was an S in play I would have looked harder). So my word had a Y acting as a vowel. First I tried R in the last spot. How about HYPER? So I built a grid using HYPER. I liked that the first down word would end in an H, for combinations such as SH and CH. After fussing with it for a while it ultimately was getting too hard to make it work, so I figured HYPER probably wasn't the word. How about CYBER? Even worse.

Next, I tried FLYER as the last word across. Not too promising having a word in the first column ending in an F, but it should be easy to rule out quickly. First word going down cannot be SCARF (a common word in these puzzles). But how the word ending in FF? FALSE would work for the fourth word across, so this was promising. I had already played with third word across and thought that it beginning with U was promising. So S_UFF...
SCUFF, SNUFF, and SLUFF were all candidate words. Next I turned to the second word across. Based on the letter placements in STORE I decided to exhaustively considered these patterns (by now, I thought the pattern _O_A_ for the second word across was more probable than _A_O_):

CODA_
CO_AD
LODA_
LO_AD
NODA_
NO_AD

NODAL and NOMAD seemed to be the most likely. NODAL turned out to make the whole thing come together.