Hi ok i didn't tested whole process yet but possibly it would go as follows
1. make new folder in templates - my template - com_k2 etc ... More info about current template placing Here
2. copy all files from default K2 template folder (/components/com_k2/templates/default) in it
3. fire up editor and change custom template files accordingly
4. set actual category to custom template in category parameters
5. also there is a one more step needed for front page to change template - to set template in menu link properties Here
As i sad i got templates to show in template selection, and i quickly changed category template a bit while writing this (just inserting some characters around) and it works. so far so good :P