I'd probably use "He, Mary, and I are going to the store."
That would make sense because we've probably already been talking about "him" (whoever that is) or you would say "John, Mary, and I..."
Please note that as the subjects of the sentence, you need "he" not "him" and "I" not "me."