The force law can be seen more as a definition than law per se. What would be the force without the equation other than just vague description?
Anyway, the force should be some quantity that tells you how the interaction between bodies affects its movement. So how to construct good, useful definition of such quantity? From Galileos experiments Newton already had notion of first law of mechanics. That is, the interaction between bodies should affect not the velocity itself, but the change in velocity. Similarly, it seemed the physics is more or less the same everywhere so the force also should not depend on position of the body.
As first attempt, the force could be just an acceleration $F=a$. But this will not do. It is everyones experience that the more heavy the object is, the more force you need to apply, where "heavy" and "force" is now used in its day-to-day meaning.
The first attempt to include the objects properties would be to introduce some quantity $m$, that needs to be determined from object to object and define force as $$F=f(m,a),$$ where $f$ is a function to be determined.
The first thing I can do is concatenate bodies together and see how the function behaves. I make some device that will produce force. I don't know how big it is, because I did not define the force yet, but if the mechanism is the same, than it is reasonable to expect that exerted force should be also the same (for example I can use the same spring for every experiment). Quickly I find that if I use same mechanism on the object with mass $m_1$, then on the mass $m_2$ and then on concatenated object with mass $m$, then I will get: $$a_1/m_1=a_2/m_2=a/(m_1+m_2).$$
This holds for any kind of mechanism we use, so we can already see additivity of mass and that it holds $$F=f(ma).$$
Now, we can just write $F=ma$, because we can always redefine $F$ by taking $F\rightarrow f^{-1}(F)$. However, such definition might not be entirely useful. We would also like to know, that if we double our mechanism of force exerting (for example, by attaching the object to two identical springs instead of one), wheter the resulting acceleration will be also doubled. And we are in luck, because experiment shows it indeed will be.
Note: The last property is actually the seed of Newton's third law, so it is not so strange of a coincidence.