4 added 638 characters in body

I'm not sure that your elementary argument is correct. Not only does the PNT not bite fast enough, but also the fact that every prime less than $k$ must divide $q$ gives only that $S(k)>(k-1)\prod_{p_i< k}p_i$, or (using the primorial notation) $S(k)>(k-1)(k-1)\#$. It is easy to show that $n\#>n$, and hence we get the lower bound $$S(k)>(k-1)^2$$ Let $l=\lfloor \log_2(k-1)\rfloor$. Then it is slightly harder (e.g. see http://godplaysdice.blogspot.com/2007/09/hand-waving-asymptotics-of-primorial.html) to show that $$(k-1)\#>\frac{(k-1)^l}{2^{l(l+1)/2}}$$

This gives us $$S(k)>\frac{(k-1)^{l+1}}{2^{l(l+1)/2}}>(k-1)^{(l+1)/2}$$ I'm not sure (barring using improved bounds for the primorial) whether these methods can get anything better.

You can regain your original $\prod_{p_i\leq k}p_i$ if you can rule out the possibility that the AP can start with $k$ itself, and this then gives you a lower bound $$S(k)>(k-1)k^{(l-1)/2}$$ where $l=\lfloor\log_2k\rfloor$.

Update: Of course, you can also gain a slight improvement by noting that the first term of the AP must be at least k, and hence $$S(k)>k+(k-1)^{(l+1)/2}$$ since if we write our AP as $a,a+q,...,a+(k-1)q$then we're trying to find a lower bound for $a+(k-1)q$. This combines our best known bounds for both $a$ and $q$. I suspect that asymptotically $q$ will behave like $k\#$, and so the $e^k$ is best possible, and the $(k-1)$ factor is fixed, so any improvements must come from better lower bounds for $a$, but these would be negligible compared to $e^k$. In summary, I think your given lower bound is essentially best possible.

3 Removed false statement.

I'm not sure that your elementary argument is correct. Not only does the PNT not bite fast enough, but also the fact that every prime less than $k$ must divide $q$ gives only that $S(k)>(k-1)\prod_{p_i< k}p_i$, or (using the primorial notation) $S(k)>(k-1)(k-1)\#$. It is easy to show that $n\#>n$, and hence we get the lower bound $$S(k)>(k-1)^2$$ Let $l=\lfloor \log_2(k-1)\rfloor$. Then it is slightly harder (e.g. see http://godplaysdice.blogspot.com/2007/09/hand-waving-asymptotics-of-primorial.html) to show that $$(k-1)\#>\frac{(k-1)^l}{2^{l(l+1)/2}}$$

This gives us $$S(k)>\frac{(k-1)^{l+1}}{2^{l(l+1)/2}}>(k-1)^{(l+1)/2}$$ I'm not sure (barring using improved bounds for the primorial) whether these methods can get anything better.

You can regain your original $\prod_{p_i\leq k}p_i$ if you can rule out the possibility that the AP can start with $k$ itself, and this then gives you a lower bound $$S(k)>(k-1)k^{(l-1)/2}$$ where $l=\lfloor\log_2k\rfloor$.

2 Simplified final inequality

I'm not sure that your elementary argument is correct. Not only does the PNT not bite fast enough, but also the fact that every prime less than $k$ must divide $q$ gives only that $S(k)>(k-1)\prod_{p_i< k}p_i$, or (using the primorial notation) $S(k)>(k-1)(k-1)\#$. It is easy to show that $n\#>n$, and hence we get the lower bound $$S(k)>(k-1)^2$$ Let $l=\lfloor \log_2(k-1)\rfloor$. Then it is slightly harder (e.g. see http://godplaysdice.blogspot.com/2007/09/hand-waving-asymptotics-of-primorial.html) to show that $$(k-1)\#>\frac{(k-1)^l}{2^{l(l+1)/2}}$$

This gives us $$S(k)>\frac{(k-1)^{l+1}}{2^{l(l+1)/2}} S(k)>\frac{(k-1)^{l+1}}{2^{l(l+1)/2}}>(k-1)^{(l+1)/2}$$ I'm not sure (barring using improved bounds for the primorial) whether these methods can get anything better.

1