Is Kinetic Energy stored as (rest) mass? I know that if some object acquires potential energy, it also gains  (rest) mass - is it the same for kinetic energy?
 A: Michael Brown's answer is correct, but is limited to the case of a single particle. (Which I guess was the intention of the question posed.) However, it is worthwhile noting that when considering two or more particles, or when considering a particle in a box, kinetic energy can increase mass. 
In other words, a box with a particle rattling around has larger mass (larger inertia and larger gravitational attraction) that the same box with the same particle at rest. The key difference with a single particle system is that a system consisting of a box with a particle rattling around does not allow a reference frame in which all components (box + particle) are at rest. For such systems mass is defined as the total energy* in the reference frame in which the total momentum vanishes**.
* as Michaels points out, an annoying conversion factor $c^2$ might need to be inserted depending on units chosen
** the frame often referred to as the center-of-mass frame
A: No. By definition the mass is the energy of a body at rest (up to that annoying $c^2$ factor ;)) and the kinetic energy is the difference between that and the actual energy. So the kinetic energy doesn't affect the mass in any way. Explicitly the energy of a free particle is
$$ E = \sqrt{p^2 c^2 + m^2 c^4}, $$
where $p$ is the momentum and $m$ is the mass. Note that this reduces to the familiar $E=mc^2$ for a body at rest ($p=0$). The kinetic energy $K$ is this minus the mass energy:
$$ K = E - mc^2 = \sqrt{p^2 c^2 + m^2 c^4} - mc^2. $$
In the nonrelativistic limit this reduces to the usual $K=p^2/2m$, but in the extreme relativistic limit $m/p\to 0$, $K\to pc$ and all the energy is kinetic energy. This is the case for photons, for example, which have no mass and yet carry kinetic energy.
A: According to the Einstein's Special Theory of Relativity, The mass of a moving object is observed greater by a stationary observer depending on the relative speed of the object with respect to the observer.
$$m=\left(\frac {m_0}{\sqrt{1 - v^2/c^2}}\right)$$
So yes, the Kinetic Energy is stored as relativistic mass(not rest mass)
