Currently, we all know how market buy order is executed when meeting only limit sell order for time-priority rule.
Two (or more) orders arriving at the same time makes no difference for an exchange's matching engine, the buy orders execute against sell limit orders, and the sell orders execute against buy limit orders. If no limit orders exist, market orders may be rejected by the exchange, or the price will be restricted to a 'volatility threshold' based on the last trade price to maintain an 'orderly' market (see section 7.3 (amongst others) of the Eurex link below).
Not to overly complicate the answer, but some understanding of matching engines and HFT is what you are really looking for here. Matching engines have several different queues to handle orders--the queues have a priority order. One of those queues is the 'Market Order Queue.' Within the 'Market Order Queue,' there will be two sub-queues -- 'market buy' and 'market sell.' The 'market buy' queue is handled independently of the 'market sell' queue.
A functional reference guide for the Eurex matching engine can be downloaded here Eurex.
Some additional resources you may learn from are:
Google Search: "Limit order book models and optimal trading strategies" will yield dozens of results.
@amdopt's answer emphasises there is a lot of depth to this topic and that the actual behaviour of the order matching depends on exchange particulars. In this answer, I give a simplified view of an exchange where market orders also don't match other market orders.
Orders can be split into two types: resting orders and immediate orders. All resting orders that have not been executed are kept by the exchange until they are completely executed or otherwise removed (for example: cancelled by the sender). Immediate orders, such as market orders, are either instantly executed or immediately removed.
So, if a market order arrives at the exchange, the matching engine of the exchange will atomically check whether the order can be matched and if it can not be matched discard the order. So it can never be that the matching engine considers more than one market order at one moment and therefore also can't match two market orders.