"Which country is Maria from?"
[country name] + 出身 (shusshin) makes a compound word, so の is not needed. 日本出身 (nihon shusshin), アメリカ出身 (amerika shusshin), and 東京出身 (toukyou shusshin) are all compound words.
どの国 (dono kuni) is a question word. It can't form a compound word with 出身 (shusshin), so it behaves like we would expect when a noun is used to describe another noun, it needs a の. It sounds terrible in English, but we're asking "Maria is of what country's origin?"
Typically surname or full name is used with 'san'. This sentence is used personal name. I do not know the situation. I think it is good that you do the same as everybody there. Or depends on the relationship with 'Maria'. This relationship is not status, but friendship and love. Or depends on character of 'Maria'. it is good you use 'san', if you worry about. 'San' is not special. Adults use to each other.
this is my personal opinion.
As you use の it should connect to a noun and cannot stand alone by itself. Otherwise you should use the Interrogative pronoun どれ.
Just a side note マリアの国 may be not a natural way to say (as it seems like she owns the country). I guess we need to say マリアの出身国.
The order of the sentence is important, and be careful of typos.
[どの] Which [おにくの] meat's [マリアは] Maria [しゅっしんですか] origin?
The topic of the sentence (the word followed by は) usually comes first.
マリアは = Maria
A word followed by の is used to modify the word that comes after it.
どの国の出身 (dono kuni no shusshin) = which country's origin
And the verb/copula comes at the end, followed by the question marker か.
ですか (desu ka) = is ?
マリアはどの国の出身すか？ (maria wa dono kuni no shusshin desu ka)
(literally) Maria is of which country's origin? = (naturally) Which country is Maria from?