Learn Portuguese (Portugal): Eles têm a mala dele no carro.

While words like seu and sua can mean his, they can also mean her, your, or their, which gets confusing. To be perfectly clear that the suitcase belongs to a man, we use dele (literally of him). Notice that it comes after the thing being owned: a mala dele (the suitcase of him).

Does dele need to match the feminine word mala?

No! This is a great feature of words like dele and dela. Unlike most Portuguese adjectives and possessives, they match the gender of the owner, not the object. Because it is his suitcase, we use dele. If it were her suitcase, it would be a mala dela, regardless of the word mala being feminine.

The subject is Eles (They). Why don't we use deles (their)?

Because the English sentence says They have his suitcase. The suitcase belongs to one specific man, not the whole group. If the sentence meant They have their suitcase, then you would use Eles têm a mala deles.

Why does the verb têm have a circumflex (a little hat) on the e?

The accent shows that the verb ter (to have) is in the plural form. Ele tem means He has, but Eles têm means They have. In Portugal, the plural têm is pronounced with a slightly longer, more stretched-out nasal sound than the singular tem.

Why is it no carro instead of just em carro for in the car?

In Portuguese, when you say in the, you must combine the word em (in/on/at) with the word for the (o or a). Since carro is a masculine word, we combine em + o to make no.