In the ring $\mathbb{Z}[\omega_p]$, the OP's second sum $\sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}$ raised to the $p$-th power is congruent to 
$\sum_{k=1}^{p-2} \left(\frac{k^2+k}{p}\right)$ modulo $p$. This new sum consists of $p-2$ terms, each equal to $\pm 1$, hence it is invertible modulo $p$ in $\mathbb{Z}$ (hence also in $\mathbb{Z}[\omega_p]$) when $p>2$. We conclude that the OP's second sum is a nonzero element of $\mathbb{Z}[\omega_p]$, which can be turned into an exponential lower bound, and perhaps even a better one (see [here][2] for a related discussion).

**P.S.** This argument was inspired by Alexey Ustinov's response to the OP's question and Noam Elkies's response [here][1], more precisely by Lucia's comment to Noam Elkies's response.

**Added 1.** As Alexey Ustinov remarked below, $\sum_{k=1}^{p-2} \left(\frac{k^2+k}{p}\right)=-1$. In fact this follows from his response to the OP's question by setting $l=0$ there and making the obvious modifications.

**Added 2.** Here is a slight variation of the above argument. The sums $\sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}$ for $1\leq l\leq p-1$ are Galois conjugates in the cyclotomic field $\mathbb{Q}(\omega_p)$, while their sum equals
$$ \sum_{l=1}^{p-1}\sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}=-\sum_{k=1}^{p-2} \left(\frac{k^2+k}{p}\right)=1.$$
Hence all the sums $\sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}$ for $1\leq l\leq p-1$ are nonzero. Moreover, their product is a nonzero rational integer, which also implies (by bounding the relevant Kloosterman sums from above) that each of them has length
$$ \left| \sum_{k=1}^{p-1} \left(\frac{k^2+k}{p}\right) \omega_p^{kl}\right|>(4p)^{(2-p)/2}.$$

  [1]: http://mathoverflow.net/questions/166297/is-weils-bound-for-kloosterman-sums-ever-attained/
  [2]: http://mathoverflow.net/questions/46068/how-small-can-a-sum-of-a-few-roots-of-unity-be