Potassium vanadium phosphate K$_3$V$_2$(PO$_4$)$_3$ (KVP) is a promising polyanionic cathodic material for potassium-ion batteries. As many other polyanionic materials KVP suffers from low electronic conductivity and shows just limited electrochemical performance. To overcome this limitation and improve the electrochemical performance, an easily scalable spray-drying process is developed to create hierarchically structured KVP/C composites. The spray-drying process leads to spherical and open porous granules of KVP particles wrapped in a carbon matrix, formed by the decomposition of sucrose and β-lactose. The influence of different carbon sources (sucrose and β-lactose) onto the granules’ microstructure is systematically studied and correlated it with the electrochemical performance of the KVP/C. The best-performing composition is employed to study different electrolyte additives with the aim to improve the electrolyte stability at high potentials in potassium half-cells.