Wordsworth begins his poem by stating how his "heart leaps up when I behold/A rainbow in the sky", and how it did this when he was a child too, and it will when he is old. So what he means by the quote "The Child is father of the Man" is simply that as a child, he felt the same awe and respect for nature that he does as a man, and how the child, in its simplicity and innocence, is often wiser than the man, and can teach the man a few things, like a father.
A major theme of a lot of Worsdworth's poetry is the beauty of childhood-he thinks that "Heaven lies about us in our infancy!", that we are closer to wisdom and God when a child than when an adult. As an adult, we don't still have that awe and reverence that children do, "The things which I have seen I now can see no more" and the world ruins us. So Wordsworth feels that the child, having more wisdom and being closer to God, can be the greater teacher, or father, to the man. So the paradox (a statement of something that is seemingly contradictory or impossible) exists because a child cannot be a literal father to a man, but, Wordsworth is saying that he is, in wisdom, perspective, spirituality and groundedness.
I provided links to another Wordsworth poem that follows this theme also ("Ode: Intimations of Immortality").
This line of Wordsworth from his "Ode: Intimations of Immortality," appears to be contradictory, but within the context of the poem, it is not, which, of course, is what a paradox is. Physically, the boy cannot be the father of a man, but emotionally, and spiritually, he can.
As he aged, Wordsworth became concerned about the loss of "secret sharers," parent-substitutes from whom and with whom a person creates. However, he later realized that he was not deprived of his sharers, for he could draw from youth with whom he also had immortal ties:
Ye blessed Creatures, I have heard the call/Ye to each other make.../My heart is at your festival.../The fulness of your bliss. I feel--I feel it all
Our birth is but a sleep and a forgetting/The Soul that rises with us,our life's Star/Had had elsewhere its setting...
O joy! that in our embers/Is something that doth live.../Of the eternal Silence truths that wake/To perish never...
Our Souls have sight of that immortal sea....
Thanks to the human heart by which we live.
In his ode, Wordsworth realizes that Youth can be inspiration to Age, and through Youth, man acquires the immortality of his ideas and truths.