The Puritans were very religious and tried to avoid the devil and evil works as much as possible. The paradox is that these very serious and religious people could be duped into believing a group of young girls and allow themselves to be taken in by their lies and actions. The girls actions also allow long simmering disputes that should have been forgiven or dealt with to come to the surface and become the motive for accusations of witchcraft that had nothing to do with the original dispute. For example, Giles Corey was convinced that Thomas Putnam is taking advantage of the trials in order to obtain more land. When Corey is accused of witchcraft, he allows himself to be crushed to death by his accusers rather than "confess" and have his land taken by Putnam. All of this devilish behavior was supposedly committed in order to get the devil out of Salem. Instead, the evil lead to the innocent deaths of at least 19 people.
In considering the paradoxes that led to this tragedy, it is worth considering why Arthur Miller chose this dark chapter in American history as the setting for a play in which he wished to explore McCarthyism. I think there are a number of paradoxes within the play (based upon true events), but in terms of a paradox that catalyzed the situation and led to the gruesome outcome, the most obvious is that the girls who were seen in the woods conjuring spirits were somehow transformed into the primary witnesses for the prosecution. In other words, the first parties to be found guilty of any actual activities that could actually be described as witchcraft became the accusers of innocent people who had wronged them. The girls were engaged in divination spells and dancing by the fire, folk magic techniques taught to them by Tituba, and it was believed these activities led to Reverend Parris' daughter Betty becoming ill or "bewitched."
Nearly all of the girls involved worked as servants and had very little social clout or power; but the justices of the court saw a way to ply their agenda by using these girls to make it seem as if there was a cabal of witches in tiny Salem Village. These girls, whose days normally consisted of hard work and drudgery, became "officials of the court" and were treated for a time with respect and awe. They continued lying and playacting in their accusations because they got caught up in the power dynamic, and the "hysteria" caused by the heightened emotions of the situation. It is this inverted power dynamic, wherein the powerless girls became powerful by becoming accusers of their pious neighbors and employers, where we find the central paradox of the Salem tragedy.