Who are all the trophies on the wall?
Well, they are the heads of the prostitutes he murdered. It appears in the comics as well.
Did they appear elsewhere in the film (or graphic novel)?
This appeared in DARK HORSE PRESENTS #59 Death of Lucille
Lucille states that creepy likes to torture and eat the body parts of his victim while making them watch. There's trophy heads of the women he's abducted mounted on the wall of this prison room, and she shows Marv that Kevin ate her hand.
From TV Trope,
In Sin City, serial killer Kevin mounted the severed heads of six of the prostitutes he's murdered and eaten on plaques and hung them on the wall.
But in movie, we only see it one or two times.
Are they just random heads, or are we meant to recognize them (even if briefly) from other parts of the stories?
It was never explained how Kevin got the prostitutes that he killed and ate, only that Cardinal Roark joined him in doing so.