When an object reaches speeds of the order of the speed of light one no longer uses Newtonian mechanics, but has to use special relativity. The the E=mc^2 is unfortunately a hybrid between Newtonian and special relativity , in order to describe the effect of force on an object moving with speeds close to the velocity of light.
The basic relativistic formula to keep in mind is the one that contains the invariant mass, i.e. a mass that is invariant to Lorenz transformations and can define a matter object :
$$m_0^2 = E^2 - ||\mathbf p||^2\;.$$
A particle, a proton let us say, has a fixed rest mass, called "rest" because it is the value the energy of the proton is in the rest frame ( momentum zero). When accelerated close to the speed of light it is the energy that changes, not the rest mass. The equivalence of mass and energy is what , when working in a Newtonian frame, responds as a classical mass to forces .
Does the increase in velocity result in an increase in the number of atoms in the object?
No. Matter (ensembles of protons and neutrons and electrons) have a fixed rest mass and the number of constituents cannot change.
The answer leads to 2)
How does mass increase if there is no increase in matter? The SI system defines mass in terms of a physical artefact (or a number of atoms, according to one proposal), but Wikipedia has seven different definitions of mass, so I'm not sure which one(s) applies here.
It only "appears to increase" if one tries to fit Newtonian physics to the interaction, i.e. work with an $F=m\cdot a$ formula.That is why the m is qualified as "relativistic". It is the total energy that is increasing with an increase of the momentum:
$$E= mc^2=\sqrt{p^2c^2 + {m_0}^2 c^4} $$
Does it make sense to ask how the added mass is distributed throughout the object?
As it is really the kinetic energy that is increasing with the increase in speed, this question is answered already.