Macbeth is full of unusual, shifting ambiguous words: it really is a play in which, as Macbeth himself says,
But what is not
It's one of Shakespeare's shortest plays and yet each line is packed with meaning which both looks forward and backward in the play.
You're right to pick up on "Fair is foul..." and there's lots of things to say about it. Like the quote I've given above, it's very difficult to tease out the precise sense: it's sort of self-cancelling (or self-affirming, depending on whether you think "fair" is both "fair" and "foul", or neither...), Macbeth currently appears "fair" (he's won "golden opinions" from all kinds of people") but will soon become "foul". The witches' prophecies sound "so fair", as Banquo says, but have another "foul" undercurrent.
"Fair", as Banquo's line "Why do you start and seem to fear / things that do sound so fair" points up, is also a close relation of "fear", and aural echoes in lines are also an important part of the paradoxical, juxtapositions of this play. Look at the way "I'll do and I'll do and I'll do" becomes Macbeth's "If 'twere done when tis done then 'twere best it were done quickly".
It's a play where you never know whether Macbeth is acting freely, or under evil influence. You never quite know what anything means. Nothing is - but what is not.
The play hinges on the paradoxes you mention because throughout the play, appearances are deceptive which is what "fair is foul. foul is fair" means, i.e., what looks fair is foul and what looks foul is fair. Lady Macbeth tells her husband in Act 1, sc. 5, to put on a false expression to keep people from knowing what he's up to. At the end of the act, in sc. 7, Macbeth himself says the same thing. After the killing of Duncan in Act 2, both Macbeth and Lady Macbeth pretend innocense. In Act 2, sc. 3, Donalbain acknowledges the fact that people are being deceptive - "...there's daggers in men's smiles." The witches take advantage of Macbeth's paranoia and need for security by giving him a false sense of security with their apparitions. The second and third visions make Macbeth feel invulnerable to attack, but it's all a trick. Even as Malcolm and the others move toward Dunsinane, they are covering their actions with the limbs they've cut down from Birnam woods giving the appearance of moving trees rather than of moving men. In the end, the battle is "lost" by Macbeth and by Scotland in that Duncan is dead, but it is "won" because Macbeth is dead and Malcolm is now king.