This is making assumptions about the nature of charge and its relation to force that are what is under discussion! We get no guarantee from nature that the force is linear in the amount of charge; if it turned out to be sqrt(charge) then we'd still have to deal with it. We could redefine charge to the sqrt of the previous quantity, but then other aspects of linearity (like conservation of charge) would have to take a different form.

We're lucky (and maybe only in the linear domain, which is more accurately the case) that these ended up being the same.

But if it were sqrt(charge) then we'd define Culoumbs constant to have commensurate units to translate sqrt(charge) * sqrt(charge) / distance^2 to force units.