Realising that there is a connection between two properties does not automatically mean that this connection must be direct proportionality. Couldn't the connection be, say, quadratic?
And that is actually the case. Work $W$ done equals kinetic energy $K$ gained (if we start at $v=0$): $$\require{cancel}W=K=\frac12 mv^2\qquad\text{ so } \qquad W \propto v^2\qquad\text{ and not }\qquad W \cancel\propto v$$
You are right that it is also true that: $W\propto m$, if we keep the speed constant.
This is not generally the case, though. This is only the case when the object is free to move, so work done only is converted into kinetic energy. If you push a stone up a hill, you can push at constant speed without any gain in kinetic energy - but you are certainly doing a lot of work.
What is the work equal to now? Sure, it is equal to the kinetic energy that would have been gained by the stone if it was free to move (with no friction, gravity etc.). But that is not useful in this case. We can't measure a speed that isn't there. We need another expression for work as well.
It turns out that such other expression is $$W=F\Delta x$$
Both expressions for work can be true at the same time - and they are not both useful in all situations.
- The work-energy theorem that states $W=\Delta K$ is only useful, if no other energy conversationsconvertions are involved. (If others are involved, then try setting up the full energy conservation equation.)
- The formula $W=F\Delta x$, or more generally $W=\vec F\cdot \mathrm d\vec x$, is always true but only useful if you know the displacement (the path) and the force at every moment along that displacement.