Yes, there is always a pure Nash equilibrium. See:
I Milchtaich (1996). Congestion games with player-specific payoff functions.
Games and economic behavior 13 (1), 111-124.
You are interested in the special case of singleton congestion games with player-specific payoff functions.
And yes, they can be computed in polynomial time. See Corollary 7 in:
This proposition is in general not true. One can show that it is true in the case $n=2$ and $m=2$. Here, I exhibit a counter example when $n=3$ and $m=2$.
A brief comment. We can rephrase the question in words: does a Nash equilibrium that is "more random" ($e'$ versus $e$) is less efficient? Intuitively, as more mixed strategies are played, the realized ...