To be clear, a working definition of a "paradox" is in order. A paradox is a statement which seems on the surface to be contradictory or absurd, yet it turns out to be make good sense.
In Marquez's story, the paradoxes begin with the title. The whole title of the story is "A Very Old Man with Enormous Wings: A Tale for Children." It is the subtitle that is paradoxical. On first read-through, this hardly seems like a "tale for children." But its moral is not unlike that of the Brothers Grimm stories: it is gruesome, yes, but lessons may be learned. The lesson here is to appreciate and not exploit gifts or miracles.
The paradoxes continue. Things are not going well for Pelayo and his family. The rains are killing their livelihood, the baby is gravely ill, and they are impoverished. Then one day, Pelayo finds a strange creature in his yard. There is no logical explanation for the winged, decrepit looking old man. And his appearance is in stark contrast to everything one would expect to find in a heavenly being.
Instead of treating this miraculous creature with reverence, the husband and wife "skip over the inconvenience of the wings." Consulting a neighbor, they are told he is an angel, but still the pair do not treat him well.
His treatment goes from bad to worse. Elisenda and Pelayo "got the idea of fencing in the yard and charging five cents admission to see the angel." After several months of this treatment, the angel manages to recover enough to fly away, "then he was no longer an annoyance in her (Elisenda's) life."
The paradox is that given the opportunity to experience the heavenly, the couple opt for the earthly sins of greed and self-interest. One should again recall the title as the tale concludes: It is not "An Angel with Enormous Wings" but an "Old Man."