If you call a contract with two different tx from different account, can they be executed and mined in the same block?
If yes how do you guarantee order and concurrency integrity like deadlocks?
[...] can they be executed and mined in the same block?
[...] how do you guarantee order [...]?
There is no guarantee. The order is selected by the miners, and while miners will normally be prone to process transactions in decreasing order of gas price, they are not required to do so.
[...] how do you guarantee [...] concurrency integrity [...]?
Miners work on local copies of the contract state, and will therefore be aware of the outcome of the previous transaction while processing the subsequent transaction(s) on the same contract.