How do we know that $F = ma$, not $F = k \cdot ma$

That's the way the unit of force is defined. One newton is the force that accelerates a mass of one kilogram by $1\ \mathrm{m/s^2}$. The newton is chosen to make the constant of proportionality equal to one.

I think it is more intuitive to say that (net) force is proportional to acceleration: $F\propto a$. The proportional constant tells us now how easy it is to accelerate an object with a certain force. This proportional constant is called the (inert) mass of said object. Hence $F=m\cdot a$.

In the Newton's Second Law, Newton basically defined what Force is. He could have taken that constant as any number that he wanted, he chose 1 for simplicity.