You have to check them one by one and then delete all together
That may work with an IMAP server, but if one is using the Email client with a POP server, once the message is downloaded, there is no sync that I know of. I too wish that they had a "select all" or, even better, an "empty trash" feature for the Email client. <sigh>Not only there is no check all.. u should not do more then 10 a time cause if you get a phone while you are checking all of them... u have to start all over..
I would erase from a pc though and re-sync the account... should be easier.