How much will using a varchar(15) PK affect my tables performance?
I don't know that the PK is your issue. To me, doing a request for all 400k rows, 15 seconds doesn't sound too bad. PKs and indexes really come into the equation when you're trying to filter the set (using WHERE conditionals).