A man approached my table. He was handsome, maybe in his thirties.

A man approached my table. Handsome, maybe in his thirties.

(Handsome, maybe in his thirties.) is a preposition, not a complete sentence. It's missing a very.

Better - A handsome man, maybe in his thirties, approached my table.

Your last example isn't grammatically correct.

A man approached my table. Handsome, maybe in his thirties.

"Handsome, maybe in his thirties." is a preposition, not a complete sentence. It's missing a verb.

This is better:

A handsome man, maybe in his thirties, approached my table.