There are two things that lead to your confusion:
1) the integral $\oint_C q(\mathbf v\times \mathbf B)\cdot d\mathbf s = vBl$ along the circuit $C$ is not $work$ of magnetic force; it is called electromotive force of the circuit (emf). This is because $\mathbf v$ in this expression is not the velocity of the charged particle, but that of the element of conductor. The charged particle moves in a more complicated way.
The work of magnetic force per unit charge per displacement $d\mathbf r$ would be
$$
(\mathbf u\times \mathbf B)\cdot d\mathbf r
$$
where $d\mathbf r$ is displacement of the charged particle and $\mathbf u$ is its velocity. Since $\mathbf u = \frac{d\mathbf r}{dt}$ is parallel to $d\mathbf r$, the above product vanishes and the magnetic force does not work on the charged particle.
2) if magnetic force does not work on the charges, then why there is current and evolution of heat in the conductor in the first place?
In macroscopic theory, the description of such situations where current is due to nonelectrostatic force (such as current in the battery, or due to thermal gradients, or due to magnetic field, as in the rod) is via general notion of electromotive intensity $\mathbf E^*$. This is not electric field, but has the same units and its meaning is that the total force acting on the macroscopic charge is
$$
q(\mathbf E + \mathbf E^*).
$$
One can derive approximate condition for $\mathbf E^*$ for the case of perfect conductor; the total force acting on the charge has to be zero and
$$
\mathbf E^* = - \mathbf E.
$$
Various circumstances lead to various expressions for $\mathbf E^*$ in terms of other measurable quantities, for example in the Seebeck effect $\mathbf E^* = -k \nabla T$. In the case of magnetic forces, experiments are well explained by assuming that
$$
\mathbf E^* = \mathbf v \times \mathbf B,
$$
but explaining why this works from the point of view of observer in the laboratory frame seems hard. It would require going into some microscopic theory of conduction and taking into account both the velocity of the rod $\mathbf v$ and the velocities of the individual charge carriers $\mathbf u_i$.
However, the above choice for $\mathbf E^*$ is well explained by the theory of relativity, if we look into the conduction from the point of view of obsever on the rod. There the electric field is composed of two parts, the electric field due to charges of the rod $\mathbf E_0'$ which from the theory of relativity is almost equal to $\mathbf E$, and the electric field due to external bodies $\mathbf E'_{ext}$, which from the theory of relativity is approximately equal to $\mathbf v \times \mathbf B$. So the total electric field in the frame of the rod is approximately $\mathbf E' = \mathbf E + \mathbf v\times \mathbf B$ and putting $\mathbf E' = \mathbf 0$ for ideal conductor of the rod and using the Ohm law for the rest of the circuit (resistance $R$), we can derive the required current $vBl/R$ and can motivate why $\mathbf E^* = \mathbf v\times\mathbf B$ works in the original frame.
Best Answer
The force from a magnetic field is given by the magnetic part of the Lorentz force equation: $$\mathbf{F} = q \mathbf{v} \times \mathbf{B}.$$
The work done by any force is given by the path integral: $$W = \int_{\mathrm{start}}^{\mathrm{end}} \mathbf{F} \cdot \mathrm{d}\mathbf{x}.$$ If we parameterize the path in terms of time we can rewrite the work integral as: $$\begin{align} W &= \int_{t_0}^{t_f} \mathbf{F}\cdot \frac{\mathrm{d} \mathbf{x}}{\mathrm{d} t} \,\mathrm{d}t \\ & = \int_{t_0}^{t_f} \mathbf{F}\cdot \mathbf{v}\, \mathrm{d}t. \end{align}$$ The integrand in the second line is one way of writing the power (rate of exchange of energy).
The point being, since the magnetic force is always perpendicular to the velocity, the integrand is always zero, so the work is zero, too. It doesn't matter if the magnetic force is the only one acting or not.
The magnetic field can store energy, though, but that energy is added to it and removed from it indirectly through the electric field according to Faraday's law.
Take the Faraday-Maxwell equation, and dot both sides with $\mathbf{B}$: $$\mathbf{B}\cdot \left(\nabla \times \mathbf{E}\right) = - \mathbf{B}\cdot \frac{\partial \mathbf{B}}{\partial t}. $$ The right hand side is equal to $- \frac{1}{2} \frac{\partial}{\partial t} \left(\mathbf{B}\cdot \mathbf{B}\right) = -\mu_0 \frac{\partial}{\partial t} u_B $, with $u_B$ the energy density in the magnetic field. Thus: $$\Delta u_B = -\frac{1}{\mu_0} \int_{t_0}^{t_f} \mathbf{B}\cdot \left(\nabla \times \mathbf{E}\right) \, \mathrm{d} t. $$