Does the mass of object really increase? We were taught the concept of binding energy,
We first started with the example of two blocks with some masses having a spring between them.
And now they are released from their position,
As they have an increase of velocity, my teacher said that their kinetic energy had increased, hence via equation, $$E=mc^2$$
The mass must have gone up,
But I couldn't digest this easily, please can anyone explain me this concept.
I think it had something to do with Einstein's relativity.
Sorry if this question has been already asked before. Thanks already

I would like to share the proof my teacher gave,

Suppose there are two bodies with mass $m_1,m_2$
Correctly written in the answers below,
We derived the eqn,
$$E_i=m_ic^2+\frac{1}{2}m_i v^2$$
Suppose two Blocks were initially at rest with spring compressed between them, let $M$ be true total mass, 
Now they are released, and they gain some $ KE$ respectively $K_1,K_2$ , 
So we can equate the total energies in Einstein's equation as following,
$$Mc^2=K_1+m_1c^2+K_2+m_2c^2$$
$$(M-m_1-m_2)c^2=K_1+K_2$$
$$(∆m)c^2=KE$$
Hence we say when the masses gain $KE$ they also lose some mass, 
But my doubts are, why didn't we consider potential energy of spring in our eqn?
Can we actually measure this mass change?
But doesn't Einstein's relativity say the masses increase when speeds increase? Is this a contradiction?

One last question,

Does the mass change in the direction of movement or in all the other directions?
i.e
Are there changes in gravitational fields of the object with increased\decreased mass?
 A: One has to define the word "mass".
It was mathematically defined by Newton as F=ma , where a is the acceleration on the object and m is invariant , a constant characterizing the object.
Then came special relativity (SR) which is necessary in order to model mathematically the behavior of particles and objects moving at very high velocities. In special relativity the Newtonian mass keeps its meaning for low velocities, but a new format had to be found for high velocities that would describe accelerations and impacts within a Newtonian set up.
This happens because in SR each particle or object is characterized by its rest mass, i.e. when not moving, and its kinematics are described by a four vector


The length of the energy-momentum 4-vector is given by



The length of this 4-vector is the rest energy of the particle. The invariance is associated with the fact that the rest mass is the same in any inertial frame of reference.

Thus for high velocities the term "mass" is defined as the m_0 invariant mass, and the E=m*c^2 is not used due to the confusions which arise as in your question. The m  in this formula is what equivalent Newtonian mass would be in impact and acceleration situations at high velocities .
Binding energy refers to the four vector representation of the kinematics of the nucleus . It is the difference between the rest masses of  nuclei, an invariant quantity at the center of mass.
The algebra of using E=mc^2 confuses the issues, though it is an important relation, stressing that mass and energy are connected. The relativistic kinematics are simpler when working at the center of mass, and thus the usage of the term mass in the E=m*c^2 is no longer stressed, and when used it is called "relativistic mass"  to be differentiated from the invariant mass of particles/objects.
Edit after extensive edit of question:

Hence we say when the masses gain KE they also lose some mass,
But my doubts are, why didn't we consider potential energy of spring in our eqn?

The potential at time t1 has become kinetic at time t2 you would be double counting if you added it at t2, and at t1 everything is static

Can we actually measure this mass change?

No, it will be very small and only relevant within the block system. Each block when hitting something would be heavier than its rest mass. Relativistic mass is not an invariant in special relativity,.

But doesn't Einstein's relativity say the masses increase when speeds increase? Is this a contradiction?

It says that the inertial mass , i.e the force needed to accelerate it according to F=ma, is higher the higher the velocity of the particle. Just an interesting algebraic relationship, relativistic mass is not a conserved quantity, energy is conserved , so in the relation
$$(M-m_1-m_2)c^2=K_1+K_2$$
M since it is a center of mass spring system and is not moving

is just the sum of the rest masses of the two blocks , so the difference
$$(∆m)c^2=KE$$
is the difference between the rest masses of m1 and m2 with their relativistic masses.
A: You can find good answers here and here. 
Just to reiterate some of the points:


*

*We generally consider the mass $m$ to be an invariant quantity, and it is explicitly called so: invariant mass.

*When a body with mass $m$ moves with a velocity $\mathbf{v}$ with respect to an inertial observer, its total energy is $E=\gamma mc^2$, where $$\gamma=\frac{1}{\sqrt{1-\mathbf{v}^2/c^2}}$$

*You can see that for a body at rest, this energy is $mc^2$, and is called the rest energy of the body. It is always there, whether the body is moving or not.

*For non-zero $\mathbf{v}$, $\gamma>1$, and the body gets additional energy (which is the kinetic energy). That is in addition to the rest energy.


You can do a small check, if you are comfortable with binomial expansions. One can write,
$$E=\gamma mc^2=\frac{mc^2}{\sqrt{1-\mathbf{v}^2/c^2}}= mc^2\left(1-\mathbf{v}^2/c^2\right)^{-\frac{1}{2}}$$
Expanding this out or very low velocities, $|\mathbf{v}|\ll c$, one gets,
$$E=mc^2+\frac{1}{2}mv^2+\text{ terms in higher orders of }(v/c)$$
The second term on the RHS is our familiar kinetic energy.
EDIT: Made corrections according to the comments by @safesphere.
A: Energy has mass. That is the idea here, it comes from relativity.
Energy E went from the spring to the blocks. From that we can conclude that mass X went from the spring to the blocks. 
If we know how large the E was, then we can easily calculate how large the x was: we divide the E by c2
The rest-mass of the spring decreased. The rest-mass of the block pair increased.

Does the mass change in the direction of movement or in all the other directions? i.e Are there changes in gravitational fields of the object with increased\decreased mass?

We have been discussing transverse mass all the time. Longitudinal mass is larger than transverse mass. 
Now, to explain what 'transverse mass' and 'longitudinal mass' mean:
An object resists attempts to change its direction of motion by its transverse mass.
An object resists attempts to change its speed by its longitudinal mass.
