Pretty much all of them do nowadays, with the exception of oddballs like Yobit--but you can't trade with fiat there anyway as far as I know.  But OP's point is that when he deposited his bitcoin, KYC wasn't required and now that he wants to withdraw it some time later, they've changed their policy and now he has to provide proof of identity in order to get his bitcoin off of Paxful (and I'm taking OP at his word, since I know nothing about Paxful other than what others have written here).

But getting a lawyer and taking Paxful to small claims court?  That's just a very expensive way of making sure everyone, including the legal system, knows you're holding bitcoin.  You'd almost be better off going through the KYC process with them than going through the courts.  If it were me, I definitely wouldn't go that route if only for the fact that getting a lawyer is likely to cost far more than $1000.  They aren't cheap, and there's always the possibility that the court won't decide in your favor.