Why is 他从商店出去了 correct but 他出商店去了 incorrect?
出 and 去 are both verbs, you can't use both as separate entities. 出去 on the other hand is a resultative verb, you can't break it up.

从 (from) is here a preposition indicating direction.

A similar expression would be 他到哪儿去了, where 到 (where/to) is the corresponding preposition.