One obvious paradox is Rahim Khan's promise to Amir that "there is a way to be good again." Rahim seems to have known about Amir's transgressions against Hassan, and he realizes that Amir's guilty conscience can only be eased by somehow finding Sohrab. However, Amir is forced to risk his life, and even when he returns home with Sohrab, he realizes his guilty conscience will never be fully erased.
Another example is Baba's flight to America, the land that he so admires. He hopes to begin a new life there and, hopefully, resume his position of power. However, Baba is never able to adjust to life in California, and loses confidence in his own abilities. The Afghani ex-patriots living in San Jose still honor him, but to the rest of the population, he is just another face in the crowd.
Another paradox occurs in Baba's own sense of honor, which he considers all-important. Yet, Amir eventually finds that Baba has kept several secrets from him: Baba has seduced Ali's wife and has fathered Hassan--a dishonorable act that he has never revealed to Amir.
Afghanistan serves as a paradox as well. The land that Baba and Amir consider so beautiful is constantly at war--first with the Russians, and then the Taliban and, finally, with Northern Alliance coalition forces. The nation is never fully united, with different factions controlling different regions.