Make them pay,
Traders might rise prices or refuse trade with them - "Sorry guys, i heard you killed brother high rank member of trades guild, so he forbid to make any deals with you, but i like you and your coins, so we can meet at evening outside of city walls, but it will cost you extra"
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 here"
Nobody wants 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 killing anyone, but those people might have families or friends who wants justice. Let them be hunted by members of Assassins Guild, City Guards or maybe army of some local Lord. Don't forget old rule :" Enemy of my enemy is my friend", some NPCs might cooperate to kill PCs.