Because 'she' is unnamed it suggests that she was mentioned just before this sentence and therefore 'She and Tommy went to the store' is better. This is because at the beginning of the sentence, she is given more importance and this position continues to give her more focus than Tommy.
Because 'She and Tommy' are the subject of the sentence you can use the plural form of the 3rd person 'they' (note: not 'them' and hence not Tommy and her') In the first sentence following, Tommy and his female companion are the object - hence 'them' and 'him'.
Alice's mother dropped them off in the parking lot and drove away. She and Tommy went to the store.
Tommy's mother dropped him and his girlfriend off in the parking lot and drove away. Tommy and she went to the store.