Why does a particle, e.g. a proton, at rest have $v=0$? Given the formula $E=mc^2$, the mass is equivalent to energy through the speed of light. This equation is also the special case of $E^2=(mc^2)^2+(pc)^2$ when $p=0$. Thus, it is at rest respectively the momentum (velocity) is zero. 
I wonder about the following: There is not really such a thing like "It doesn't move at all" since particles are also waves, somehow. Therefore, I think, particles like protons still provide some kind of velocity though they do not really move at all.
Is that true? And if so, what is their speed and how can it be estimated?
 A: You are correct that having a particle completely at rest is impossible, because of the uncertainty principle: the uncertainties in position and velocity must be related by $\Delta x \Delta v \geq \hbar/2m$. So whenever we say that a proton is at rest, we are doing an approximation: we are neglecting the uncertainty in velocity, compared to other quantities involved.
One situation this happens is when we take a macroscopic point of view. For example, maybe we want to roughly calculate the path of the proton inside a particle accelerator. If we only care about overall quantities like, say, the radius of its orbit in a given magnetic field, QM is not very important: the uncertainties in position and velocity are much smaller than the quantities involved, and simply using classical special relativity is enough.
Another example, this time quantum mechanical, is the treatment of the hydrogen atom. A proper calculation mirrors the classical (Kepler) two-body problem, and uses the center of mass coordinates and reduced mass and so on. But a closely related approximation simply considers the proton to be at rest, since for the proton and electron we have
$$\Delta x_p \Delta v_p \geq \hbar/2m_p \qquad \text{and} \qquad \Delta x_e \Delta v_e \geq \hbar/2m_e.$$
Given that $m_p$ is around two thousand times $m_e$, the right hand side of the proton's uncertainty principle will be correspondingly smaller, so we would roughly expect the uncertainties to be smaller as well, and as a first approximation we can neglect them.
A: The theory of special relativity (TSR) doesn't know about quantum mechanics at all.
In TSR when you change your frame such that the proton is at rest, it is truly at rest with $v=0$ in the framework of this theory.
'Reality' in physics doesn't exist, only models of it, that describe it at hopefully better and better accuracy.
Of course you could ask then, what does the merge of TSR and Quantum mechanics (a.k.a. Dirac mechanics) have to say about $v=0$ in the rest frame, but there I'm out of my depth.
