Why will this system execute simple harmonic motion? For a particle to exhibit simple harmonic motion, the force acting on it always has to be $\vec{F} = -k\vec{x}$. But here:

Let's say it has some initial elongation. Now, the only way it would have $\vec{F} = -k\vec{x}$ is if it was pulled down by some distance $x$ since the tension in the string connected to the string can only pull, not push. But when the block is moving up and passes the mean position, there's no restoring force $-kx$ on it(A string can't exert such a force).
How does this system show SHM?
 A: A motion is called simple harmonic motion (SHM) if it is a solution of the SHM equation,
$$\frac{d^2x}{dt^2}+\omega^2x=0.$$
It is not necessary that the force is strictly $\vec F=-k\vec x$. It can be for instance $\vec F=-k\vec x+\vec c$, where $\vec c$ is any constant force. In the later case, the equation of motion reads
$$m\frac{d^2x}{dt^2}+kx=c.$$
Simply changing variables $y=kx-c$ gives the equation
$$\frac{d^2y}{dt^2}+\omega^2y=0,$$
which defines SHM. In your example, the constant force is just gravity.
A: I see what you mean : a compression force cannot be transmitted to or from the mass because strings and wires can only transmit tension (stretching) forces, not compression forces.
However, in the mean (equilibrium) position the spring is in tension $(T=mg)$ and has extended by $x_0=mg/k$ beyond its natural length. Provided that the amplitude of motion is less than or equal to $x_0$ there will always be a tension force in the spring $(T>0)$, and a downwards restoring force $mg-T$ on the mass, because $mg>T$ when the mass is above the mean position.
What you say is correct. $T$ cannot fall below zero. If the mass goes more than $x_0$ above its mean position then the spring will not be compressed. The restoring force is then only $mg$. It is constant, no longer proportional to displacement, so this part of the motion would not be SHM. 
A: In the static equilibrium position the spring is in a state of tension with extension $z_o$.
Provided the amplitude of oscillation is less than $z_o$ the spring will always be in a state of tension.
So if this condition holds the spring will never be compressed (pushing) and the motion will be simple harmonic just like the usual spring-mass arrangement.
All the pulley does is to change the direction of the force exerted by the spring.
A: Pull $m$ down and thereby stretch the spring. By Newton's third law, the spring exerts an equal and opposite force on $m$. Indeed if a spring stretched $\mathbf{x}$ beyond its equilibrium has potential energy $\frac{1}{2}kx^2$, expressing the stored potential energy as a line integral of force implies $m$ pulls on the spring with force $k\mathbf{x}$. Thus the spring pulls on $m$ with force $-k\mathbf{x}$. The same logic applied to the stretched end of the spring explains why that endpoint experiences simple harmonic motion.
