As a native Portuguese, I must say this should be "Desculpe, (você) fala português?"
"Com licença" is used after one has been granted permission (license) to do what one has requested. Hence, literally saying "With license" or "Com licença". It's mostly a formality for when someone holds the door for you or lets you go in front of them.
Since you're just asking a question, you'd just apologize for inconveniencing the other person before asking it.
Could you say "fala voce português"? Does verb order matter in Portuguese?
Verb order does matter. "Fala você português?" places the emphasis on "você", as if a group were deciding who would speak which language ("you're the one who speaks portuguese?"). However, as an isolated question is sounds bizarre and/or clumsy, much like "speak do you English?"
In other places from Europa, it happens same thing. In italian, we'll use "mi scusa", while in german "entschuldigung".
Yes and no. Using "sorry" instead of "excuse me" isn't correct if you're asking a stranger on the street, for example. It would sound more like a snappy remark, kinda like "OH, I'm sorry Becky, do you speak portuguese? No, you don't!"
In Portuguese you'd use "desculpe" or "desculpa" for both situations, it's all in the tone.