Must there always be a normal element with non-discrete spectrum in an infinite-dimensional C*-algebra?

Yes it is true. As mentioned in the article you linked to in the Remark on page 4, every infinite dimensional C*-algebra contains a self-adjoint element with infinite spectrum. (In context it helps to know that every C*-algebra is semi-simple.) A reference is given to Ogasawara's "Finite dimensionality of certain Banach algebras," which doesn't appear to be readily available online. (I do not have a more easily accessible reference or proof off hand.) Note that the only compact discrete subsets of $\mathbb C$ are the finite subsets, so your two questions are the same.

The operators on an infinite-dimensional Hilbert space of the form $\alpha I + K$ where $K$ is a compact operator form an infinite-dimensional $C^*$-algebra in which every element has discrete spectrum.