Why does the reaction between Na (s) and Cl2 (g) occur spontaneously if the entropy of the system decreases?
As you point out there are two things to consider, the heat released in the reaction and the change in entropy. In forming NaCl from chlorine gas and solid sodium the entropy decreases because the gas is converted into solid NaCl which has a far far smaller total volume. The energy released has the effect of heating the solid NaCl just formed and then the surroundings as energy flows away to eventually reach equilibrium again but now at a higher temperature than that at equilibrium before reaction occurred.

When a quantity of heat $dq$ from a body at $T_2$ transfers to one at $T_1$ the overall entropy change is $dS = dS_1 + dS_2 = dq/T_1 - dq/T_2$. As $T_2 \gt T_1$ the entropy change is positive. 

In the reaction the entropy change overall depends on comparing that decreased due to volume decrease vs. that increased due to the energy released on reaction.

Entropy is a measure of the number of ways that the particles can be placed into their energy levels, this is often called the number of configurations $\Omega$, and Boltzmann found that $S=k\ln(\Omega)$ so that increasing the distribution of energy into the energy levels increases $\Omega$ and hence S. As the temperature increases more vibrational and rotational levels are populated and the kinetic energy distribution widens, all this means that there is an increased number of configurations and hence entropy just because energy can be placed into  energy levels and in more ways. 

If there was just one level then all 'particles' would have to be in this level and so entropy would be zero, $\Omega=1$.  When there are two levels some can be in the first and some in the second level and now the entropy is increased ($\Omega \gt 1$), and so on for many levels.