Make them pay,
Traders might rise prices or refuse trade with them - "Sorry guys, i heard you killed the brother of a high rank member of trades guild, so I am not allowed to make any deals with you, but I like you and your coins, so we can meet at the evening outside of the city walls, and it will cost you extra money for the risk being taken."
Bartenders will keep their inn closed for them, -"I know what you've done to that poor lad, we don't want people like you in here."
Nobody (except, probably, evil characters) wants to teach them new skills, -"I will never teach people like you, you will bring shame and dishonor to me and my school"
Make them run,
They can kill anyone, but those people might have families or friends who want justice even if they can't accomplish it themselves. Let them be hunted by members of the Assassins Guild, City Guards or maybe army of some local Lord. Don't forget the old rule: "Enemy of my enemy is my friend", some NPCs might cooperate to kill the PCs.