You ask
Why did the author use "that" after the adjective "paradoxical"?
How paradoxical is an exclamation.
Exclamations often have no explicit verb. The verb is implicit:
{something} IS so very paradoxical.
What is the "something"?
In your sentence, the that-clause is the "something"; the that-clause is the subject of the verb IS which is implicit in the exclamation:
That the world's great chefs have all been men
IS
(so very) paradoxical.
We could also make that sentence using it as a kind of placeholder for the content supplied by the that-clause:
How paradoxical it is, that the world's great chefs have all been men.