Коце Паунов е роден в град Кочани, тогава в Османската империя, днес в Северна Македония. Заклет е във ВМОРО през 1895 година от Гоце Делчев и оттогава е дългогодишен член на околийския революционен комитет.[1] Освен него в комитета влизат Димитър Наков, Глигори Емануилов, Йордан Зомбата, Тодор Наков, Коце п. Захариев и Георги Чакъров.[2] При разразилата се Винишка афера от 1897 година е арестуван и заточен на каторга в Мала Азия.