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.
P.S. Compare the following where the that-clause is the subject:
That the Ferrari is a fast car is undisputed.
That a triangle has three sides is a basic fact of geometry.
That the starving sailors had resorted to cannibalism was not released to the public.
How gruesome, that the starving sailors had resorted to cannibalism
How interesting, that this fact had not been released to the public.