later I can't say too much, but I'd start with the real triple $[C^{1/3},C^{1/3},C^{1/3}]$ then round up and down to integers and try small variations. I don't think you'd go too far from there. Here are all the best triples from [15,15,15] to [16,16,16] so if you want C between 3375 and 4096 you'd pick one of these.
For positive real values of $x,y,z,C,K$ the problem has an easy solution $x=y=z=\sqrt[3]{C}$ with $K=3C^{2/3}$ (If $K$ is any smaller there is no solution). In the integer case, if C is a perfect cube then the same can be obtained. And in any case, restricting to $x,y,z$ equal integers still gives a solution provided that $K \ge 3C^{2/3}+6C^{1/3}+3$. Actually you can do slightly better that by allowing $x \le y \le z \le x+1$.
That does leave some pairs $K,C$ still unexplained.It might be worth studying which integer triples $x_0,y_0,z_0$ are such that no other $x_1,y_1,z_1$ has $x_1y_1z_1\ge x_0y_0z_0$ and $x_1y_1+x_1z_1+y_1z_1 \le x_0y_0+x_0z_0+y_0z_0$