Most centralized exchanges will require KYC/AML.
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.
2. you will not find a new york lawyer who will take your case anonymously - will not happen, when you share your info with lawyer - they will share with gov't . In america there is no "lawyer-client" privilege - not in practice since 9/11. Anything AML/FATCA is considered national security and all info will be shared by lawyer.
Are you absolutely certain of that? Because there is--and always has been (AFAIK)--attorney-client privilege in the US, and I've never heard of exceptions being made for financial matters. What you said just doesn't sound right.