Why was the AC Stark effect only discovered after the laser was invented?

The answer is photon statistics. Before the invention of the laser, i.e. with thermal light sources the mean photon number occupation per mode is $$ bar{n} = frac{1}{e^{frac{hbar omega}{k_B T}} - 1} text{.} $$ Using a hot $T = 8000,text{K}$ arc lamp there are only $bar{n} = 0.107$ photons per mode around the D₂ transition frequency of $omega = 2pi cdot 389 ,text{THz}$. After filtering and all the optics it would be reasonable to assume that maybe $0.01$ photons per mode actually make it to the Potassium vapor cell.

For any nonlinear effect like the AC stark shift both, the pump and the probe photon, must interact with the observed atom within a short time interval. Hence, with only $1/100$ photons from each beam, the chances of a nonlinear interaction is $sim 1/10000$. This might be observable with equipment from the 1960s if you had a lot of signal (high intensity), but again the power is the problem.

In contrast, in the paper they produce pulses (of presumably one or only few modes) with a peak power of $1 ,text{MW}$, that's $10^{17}$ photons within the pulse of "10^–8 – 10^–7 sec" duration. So even with a highly multimode laser pulse the strength of nonlinear interactions is many orders of magnitude larger.

What do I mean by mode? And why are they important?

A Fourier-limited pulse is called "single mode", while a pulse of the same duration, but with twice the spectral width would be a two-mode pulse. Analogously a TEM00 Gaussian beam is a spatial single mode, while an incoherent mixture of a TEM00 and a TEM01 beam is two different modes, because the spread in tranversal wavevectors is larger than for a single-mode Gaussian beam of the same waist.
More generally, the 6-dimensional configuration space (position vector $times$ momentum vector) can be tiled by Fourier-limited tiles (of any shape) within which particles are indistiguishable. For photons you need to consider a 7th dimension, polarization. Each tile represents a mode, together they form a complete orthogonal basis for the phase space.^[1]

I'm formulating this so abstract, because the number of photons per mode can only be decreased by linear optics, like lenses and beamsplitter, but never increased. This is independent of the choice of basis to represent the modes. I think for the frequency, it is pretty clear that there is not linear device taking in photons of multiple different frequencies and outputting the same number of them converted to a single frequency. For the distribution of transversal extent and wavevectors the conservation of photon number per mode is probably better known as the conservation of étendue, which is the phase-space equivalent of Liouville's theorem. I gave 3 different explanations of it in "Is it possible to construct a lens which focuses all the light rays from an extended object in one point?" and it is the reason why the answer to "Is it possible to start fire using moonlight?" is no.

This case

Let's choose a basis for the modes, in which the interaction of an atom with light can be described by a single mode. This is typically the picture people use nowadays, because everybody works with lasers, which emit only a single mode of light.

The mode of interest in this case is the one which matches the radiation pattern of the atom. Spatially, this is the classical dipole emission pattern. Only the part of the light inpinging on the atom in this shape can interact with it. More rigorously one needs to calculate the overlap integral of the ingoing mode with the dipole emission mode.

In the time domain the mode of emission is an expoentially decaying pulse, which is the spectral domain is a Lorentzian. Again, only light which matches this mode interacts with the atom. (Side note: If the mode of light exactly matches the time-reversed spontaneous emission, a single photon can excite the atom with 100% probability.^[2]) The spectrum of the D₁ and D₂ lines of potassium have a linewidth of $Gamma = 2 pi cdot 6 , text{MHz}$,^[3] which is extremely narrow compared to the blackbody spectrum emitted by an arc lamp (hundreds of $text{THz}$).

Let's do the above calculation of photons per mode in a more classical way: Optimistically assuming one can build an experiment in which the spatial mode matching is as good as if the atom is placed directly on the surface of a blackbody, i.e. it is illuminated from a solid angle of $2pi$. Then we only have to care about the spectral overlap. The power per surface area per frequency interval $d nu$ emitted by a blackbody in $2pi$ solid angle is $$ 2pi frac{2 h nu^3}{c^2} frac{1}{e^{frac{h nu}{k_B T}} - 1} d nu text{,} $$ that is $5.856 cdot 10^{-7} frac{text{W}}{text{m}^2 text{Hz}} d nu$ for the above used parameters. So in a $d nu = 6 , text{MHz}$ wide frequency interval it is $3.514 frac{text{W}}{text{m}^2}$. Within the scattering cross-section of a single atom $sigma_0 = frac{3 lambda^2}{2pi}$ this is $9.728 cdot 10^{-12} , text{W}$ or $3.771 cdot 10^6 , text{photons/s}$. The number of photons interacting with the atom per excited-state-lifetime $1/Gamma$ is therefore $bar{n} = 0.101$.