Picture you have both of these on a location and you are the first player. You currently do not have any allies in your hand.

You explore the location and choose to resolve the Ancient Mathom effect first and draw 3 cards. You now draw an ally.

Are you able to then resolve the response on Elfstone to play said ally from your hand? Or has the exploration already resolved and thus it is too late to trigger Elfstone?

You can chose which response triggers first. So yes, you can play the ally

Caleb said in an official answer that the wording of Ancient Mathom can be read "After attached location leaves play as an explored location", the same as Elfstone.

So the trigger is the same and you can resolve the effect of elfstone after drawing your cards : http://boardgamegeek.com/thread/762544/question-about-the-card-valiant-sacrifice-core-set/page/2

That's good, stargazer with those attachments has just got that much better for me.