I know that paid traffic is not allowed in AdSense, but what if I paid for Adwords and Yahoo search marketing for traffic? Are they allowed?
As long as you will not try to get cheap traffic from adwords to cash more on your adsense with them you should be fine. I saw big networks that do it without major problems but from time to time they get banned. It's a risky thing but doing it "right" will bring in a lot of money, you can't know for how long though.
I think by no paid traffic, they mean no paying for random traffic. If you're marketing to your niche, I don't think they'd have a problem. As long as its genuine advertising and not just paying for impressions. So yes, search marketing is allowed.
Maybe not random, but some fake traffic (made by poupups and forced and misleading redirections) is disallowed - for sure. I don't think that should be anything against good traffic even it is paid (for instance: from advertisiments campagains).