Here is a sketch of a 4-dimensional counter-example where you allow $M$ to have boundary. The motivating 2-dimensional version of this construction is as follows:
Take $N$ which is the surface of revolution obtained by rotating the graph of $y=e^x + 0.5$ around the $x$-axis in $R^3$ (with the induced Riemannian metric). Notice that the infimum of lengths of embedded homotopically nontrivial loops on $N$ is $2\pi$ and it is not realized by any loop. Take $M$ which is the product annulus $S^1\times [0,1]$, where $S^1$ is the unit circle. Then the infimum of 2-energies of homotopically nontrivial maps $M\to N$ equals the area of $M$ but it is not achieved. As @Litho correctly noted, nevertheless $E(M,N)=0$ since you can take homotopically trivial embeddings. (Nevertheless, this is an example if you require immersions to be homotopically nontrivial. )
Similarly, if you consider connected oriented 3-manifolds and $M$ has nonempty boundary then $E(M,N)=0$ (since one can immerse every such $M$ in $R^3$).
To get the actual example, we go one dimension up. Let $M$ be a simply-connected smooth compact non-spin oriented 4-manifold with boundary. Then $M$ does not admit immersions in $R^4$.
For concreteness I will take $M$ to the complement to a 4-ball in $CP^2$. Then $M$ has structure of a disk bundle over $S^2$
(with the Euler number 1). I will equip $M$ with a Riemannian metric such that there is a fibration $M\to S^2$
over the round 2-sphere (of the unit radius) which is a submetry. I think (but I did not check this), the least 4-energy map from $M$ to such
$S^2$ is given by the projection $p$, in which case, $E(M, S^2)= Vol(M)$.
Now, take a 4-manifold $N$ which is diffeomorphic to an infinite connected sum of $CP^2$'s. One needs to choose a suitable Riemannian metric on $N$ such that the $k$th $CP^1$ admits a neighborhood isometric to a rescaled (by $\lambda_k>1$) version of the above example with $\lambda_k$ converging to $1$ as $k\to \infty$.
We then have a sequence of immersions $f_k: M\to N$ whose 4-energies converge to $Vol(M)$ from above (without ever reaching it). One still needs to check that there are no immersions of smaller 4-energy. I do not see any possible candidates but proving this would require much more work that I can afford.
The real question, I think, is about maps between closed manifolds which then are necessarily finite covering maps.
A paper to read is
B. White, Homotopy classes in Sobolev spaces and the existence of energy minimizing maps, Acta Math. 160 (1988), 1-17.
Or you can simply email Brian (he is at Stanford): He is a very nice guy and will help if he can.