Motion of a particle

It seems like the way you phrase the question is making it confusing for yourself. You basically ask: kinetic energy can increase if work is done (work-kinetic energy theorem), and also in order for work to be done, there must be displacement ($f cdot dx$). How much work is required for a particle to go from 0 velocity to some small velocity?

The way you phrase it makes it seem like you might need a LOT of force, because the force is applied over a distance that is (almost?) zero. However, you should consider that the velocity change is also very small ($dv$). In order to do this much work, you only need to apply force over a very small displacement that is also almost zero ($dx$). So in reality, the work needed to go from $0$ velocity to some velocity is very small, not very large.

Once that is established, it still seems like a chicken-and-egg problem, you need speed to do work, and you need work to get speed. The reality is pretty simple though, what you're missing is that once some force is applied, the response (acceleration) is instant, there is nothing to stop it from moving. Its not a chicken-and-egg problem, because both happen simultaneously.

Another way to think about it is simply: what if the particle does not start off at rest, but starts off moving at constant speed? In that case, the result is obvious. However, there should be no difference, since that is effectively only a change between inertial frames.

The force should be responsible for supplying velocity or rather kinetic energy to the particle through work.

No, the force is responsible for supplying velocity directly as second Newton law of motion says. $F=ma$ is the central concept that describes mechanism behind motion of bodies, not $Delta E_k=FDelta s.$ The energy equation just says the two numbers are ought to be equal.

Also, your formulation is not very good. You should talk about power instead of work, because the power is quantity that has meaning for every single instant of time, while work is change between two times.

The Zeno's paradox with the arrow explains this better. The flying arrow cannot move as it is at rest in every single moment of time. And since we do have photocameras in todays age, we know that the arrow indeed does not move on our photos, which captures the single instance. Yet, rarely anyone is confused by this nowadays.

The difference is, that Zeno is thinking in terms of position and he sees motion as changing position. This position is obviously not changing in single moment, so there is no motion. We however know, that change in single moment is nonsensical idea and that the central concept is not change in position but rather rate of change of position (velocity).

The work is analogous to change in position. The true quantity which captures the transfer of work at single instant is power. This power is zero for object at rest, since $P=Fv$ and $v=0$. So better formulation of your problem is: "How is it possible for object at rest to start moving, if the power on it is zero unless it moves already?"

And the answer is, that you should be more careful not to confuse motion with energy transfer. Just because energy is not transferring at some instance, does not mean that object is not accelerating at the instant:

$$0=Fv=frac{dE_k}{dt}=mva,$$ So zero power implies either $v=0$ or $a=0,$ not only $a=0.$