Lets discuss the electromagnetic case first, it's much easier. First, let's look at what the force law in electromagnetism between two charges actually is. You've noticed that it is not K q1 q2 / r^2.
The law we are need is the Lorenz force law, which is ##f = q(E + \vec{v} \times \vec{B})##. This is called the Lorentz force law, see for instance
https://en.wikipedia.org/w/index.php?title=Lorentz_force&oldid=678002831
E and B are the electric and magnetic fields. This law currently isn't in the form of the "force between charges". To apply the law to get the force between charges, we need to find out what the E and B fields are generated by a charge.
The exact expression of this is rather complex. I'm not sure of the simplest, most basic presentation. The one that comes to mind at the moment is the idea of the "retarded potential",
https://en.wikipedia.org/w/index.php?title=Retarded_potential&oldid=667679850, which winds up yielding Jeffmenko's equations,
https://en.wikipedia.org/w/index.php?title=Jefimenko's_equations&oldid=598903545. This is probably too advanced in detail, since this is an I level question :(.
Another approach that comes to mind is a discussion of "how the electromagnetic force transforms". This yields some good insights though it doesn't really answer the question of what the EM field of a moving charge actually is in numeric detail. Since it doesn't cover the point needed, I'll skip giving a link for that, if there's some interest, ask.
The motivation for all this is perhaps simpler, and perhaps it will satisfy you as to why we need both the E and B fields to define the force between charges. The motivation is that we want the laws of physics to work in any reference frame, so that we get the same result in a frame where the first charge is stationary (and the second is moving), a frame where the first charge is moving and the second is stationary, or an arbitrary frame where both charges are moving.
This principle is called the principle of covariance.
So we can say then, in general, that the observed behavior of the electromagnetic interaction, which involves both electric and magentic fields, is compatible with special relativity because the physical laws (including the force laws) are relativistically covariant. And we can note that the coulomb force law you ask about ##F = k \, q1 \, q2 / r^2## is NOT relativistically covariant.
I'm not sure how much further we can go in an I level thread, really. A textook like Griffiths, "Introduction to Electromagnetism", will go through the electromagnetic force in detail, both from a classical viewpoint (using Maxwell's equations), and a purely relativistic treatment. To follow the relativisitc treatment in full, though, you'll need to learn enough special relativity to understand relativisitic kinematics (the Lorentz transform) and relativisitc dynamics (the treatment of forces in special relativity). It's also helpful to realize that Maxwell's equations are fully compatible with special relativity, and that Maxwell's equations can be regarded as inspiring special relativity, though I wouldn't claim that this is historically accurate.
[add]
Let me just point out here that there is a bit of a change in thought here, from the idea of a force between charges, which in the coulomb case instantaneous, to a field concept, where the charges radiate fields, the fields propagate at some velocity, and then the fields interact with charges after they propagate.
Now let's say a few words of what additional things we need for gravity. If we consider only linearized gravity, there's a theory called GEM that is very like Maxwell's equations that gives us a gravitational equivalent of a "magnetic force" along with the usual "coulomb-like" force you're familiar with. If we want to go deeper than linearized theory, we start running into the limits of the idea of describing gravity as "just a force". Gravity causes effects such as time dilation and changes in the spatial geometry that simply cannot be put into the "mold" of a force. Thus any treatment of gravity that treats gravity as "only a force" doesn't even have the concepts to describe these additional effects.
The pop-sci version of this is to say that "gravity is curved space-time". But do yourself a favor and skip over the ubiquitous bowling-ball-on-a-sheet picture, which is rather likely to give you some false ideas :(.