Is there any way to add custom category icons for the different categories, and have them show up in the templates?

that would be completely another component IMHO
in order to achieve similar effects you may customize your templates with CSS to display the category image in stead of icons, this is "fake" but k2 natively supports this.
a little hacking on the scripts might be needed, but i think this should not involve any change beyond the templates folder. see also "k2 templating" on this site as well as k2joom.com
good luck