You can use *a, but this only selects conversations on the current page. I'd like to select all conversations without using the mouse, IE to delete hundreds of emails from a specific sender.
I can't find a way to do this easily without the mouse, the "Select all conversations..." link isn't even selectable by using the Tab key, so you can't get around it that way.
I think the best you can do is keep on pressing *a, then #, then *a, then #...
This isn't really a general solution, but for situations like your example, you could set up a filter using the search, then apply it to existing messages.
Click "create filter" next to the search button.
Fill in your search criteria. You can click "Test Search" to make sure you are only getting what you want.
Once you've selected the messages you want, click "Next Step".
Choose the actions you want to perform. You will also want to check the box that says "Also apply a filter to n conversations below".
Click "Create Filter".
If you don't want to keep doing the action automatically in the future, you will need to delete the filter. You can find all your filters in the "Filters" tab in your settings. The last one you created should be at the bottom of the list.