Cillian /
Killian wouldn't be bad, if it didn't remind me of that alcoholic beverage
Killian's Irish
Red. As for your questions:
Yes, I can see the "kill" beginning being an issue with some idiots.
I wouldn't worry about any perceived similarity with female names. Julians and Adrians seem to get along just fine.
Definitely use the K spelling, as very few Americans would recognize the correct C prn.
BTW, I'm an American of Irish heritage.