- A paradox is a situation, so the adverb "paradoxically" does not describe a person or a thing. In both of the examples you cite, the adjectives refer to the object or person.
Look at another adjective as an example - let's use the word brilliant:
How brilliant the world's greatest chefs are!
Here "brilliant" is describing the chefs themselves. They are brilliant.
How brilliant that the world's greatest chefs are men!
Here the word "brilliant" is not describing the chefs, but the situation in which all the world's greatest chefs are men. That is needed to introduce the clause that follows to show that it is the situation that is paradoxical, not the chefs.
- The word "would" is sometimes used to make a sentence less direct.
For example:
I expect you to be home at 4pm.
I would expect you to be home at 4pm.
The first is very specific - the person expects you home at 4pm. It could even be taken as a demand that you must be home at that time. The second sentence, however, is looser; it implies that this is the time they would expect, perhaps under usual circumstances or thereabouts.
Likewise, in your sentence, the writer is trying to establish that a paradox exists. They are suggesting that cooking is normally something associated with women, and yet most of the greatest chefs are men. It would seem odd to first make a bold statement that the world's greatest chefs are men, and then make an equally bold but contrary statement that cooking is "exclusively within women's realm". I believe the writer has used the word "would" to soften the statement, and imply that this is what you would normally expect rather than what is definitely the case.