Hebrew Wikipedia has an extensive discussion on the matter.
Also see Chapter 2 of יופי של עברית by אבשלום קור
, כהנא, כגן, קוגן, קגן, כגנוביץ, קאהן, קון ,קיהן, כהנמן, כוהנר, ברכגן, ברקן , קצמן, כצובר
Kahana, Kagan, Kogen, Kagen, Kagnovitch, Kahan, Kohn, Kihan, Kahanamen, Kohner, Brechgan, Barkan, Katzman, Katzover (the last two being later extensions of Katz)
The 'g' sound comes in place of the 'h' sound in Slavic languages.
מזא"ה (= מזרע אהרן הכהן)
Maza - MeZera Aharon HaKohen (from the descendants of Aharon the Priest)
Hadad - according to the community of Jews from Djerba, Tunisia, Hadad is a Kohen family which was disqualified (because of inappropriate marriages)
זלכה - זכר לכהן הגדול
Zalka - common among Iraqi priests, Zecher LeKohen Gadol - in memory of the high priest
Gindi - among Jews from Halab (Aleppo), Syria this is a priestly family
Rappaport - many of them descended from the author of the Shach ש"ך (a book which itself means שפתי כהן, lips of the priest). (See for instance, Rabbi Shabtai Rapaport, a teacher in Bar Ilan University).
כהן אברי"ש - אני בן רבי ישמעאל
Avrish - Ani ben Rabbi Yishmael (I am the son of Rabbi Yishmael) - according to legend, this family is a descendant of Rabbi Yishmael the High Priest.
Kaplan - from the same Latin root as 'chaplain'
תומא הכהן - תורה וברכת משרתי אל
Tuma - Torah U'Birkat Meshartei El (Torah and the Blessing of the Servants of God) - a priestly family living in Pekiin since the Second Temple
Malamud - priestly family from Shiraz, Iran with a number of scholarly descendants (of course most Malamuds are not priests)
כהן ירמו"ש - יורו משפטך ליעקב ותורתך לישראל
Yarmush - Yoru Mishpatecha LeYaakov, VeToratecha LeYisrael - Teach your laws to Yaakov and your Torah to Israel - a quote from Yaakov's blessing to the tribe of Levi
Yonatan - family of Algerian priestly Jews
Tanugi - family of Moroccan priestly Jews from Tangier
Al Magerbi - family of Tunisian priestly Jews from Djerba. Name is from the Tunisia's region in North Africa, commonly known as the Maghreb
Some funny stories --
In the 9th Knesset, Yigal Cohen was elected as a representative for Likud - except they already had a Yigal Cohen in the Knesset! So the first one changed his name to Cohen-Orgad כהן-אורגד (Orgad being the initials of the names of his children)
In 1980, there were two soccer players on the same team named Eli Cohen. So the newspapers simply referred to one as אלי כהן הקטן (the small Eli Cohen) and אלי כהן הגדול (the big Eli Cohen).
There are many cases in history (as seen above) and in modern Israeli life where individuals with the last name Cohen hyphenated their names in order to be more easily identifiable.