Let $R$ be an algebraic number ring with class group $C(R)$, and let $x : C(R)$. Then there exists a prime ideal $P$ in $R$ such that the ideal class $[[P]] = x$, and in fact there are infinitely many such prime ideals.
What about if $R$ is an arbitrary Dedekind domain? Does every ideal class have a prime ideal representative? If this is not true for arbitrary Dedekind domains, what about if we restrict to rings where $C(R)$ is finite?
Some authors add the requirement that a Dedekind domain not be a field. I will assume that a Dedekind domain is not a field, since otherwise any field is a counter-example.
The answer is no: there are Dedekind domains with finite and non-trivial class groups but no non-zero prime elements. In the class group of such a Dedekind domain, the trivial class cannot be represented by a prime ideal.
Claim. Let $R$ be a Dedekind domain and denote by $\operatorname{Cl}(R)$ its class group. Let $S$ be the multiplicative subset of $R \setminus \{0\}$ generated by the non-zero prime elements and the units of $R$. Then the localization $D := RS^{-1}$ has no non-zero prime elements. Furthermore, the group $\operatorname{Cl}(D)$ is trivial if and only if $\operatorname{Cl}(C)$ is trivial.
By localising appropriately a Dedekind domain with a finite non-trivial class group (e.g., $\mathbb{Z}[\sqrt{-5}]$, the ring of integers of $\mathbb{Q}(\sqrt{-5})$), we obtain thus a counter-example.
We will need the following lemma.
Lemma. Let $R$ be an integral domain with ACCP and let $S$ be the multiplicative subset of $R \setminus \{0\}$ generated by the non-zero prime elements and the units of $R$. Then the localisation $D := RS^{-1}$ has no non-zero prime elements. Furthermore, a height one prime ideal $\mathfrak{p}$ of $R$ is principal if and only $D\mathfrak{p}$ is a principal ideal of $D$.
Proof of the Lemma. To show that $D$ has no non-zero prime elements, we reason by contradiction, considering $p \in R \setminus \{0\}$ such that $p$ is a prime element of $D$. Since $R$ satisfies ACCP, we can assume, without loss of generality, that $p$ is irreducible in $R$. Let $a, b \in R$ be such that $p$ divides $ab$ in $R$. We can also assume, without loss of generality, that $p$ divides $a$ in $D$. We claim that $p$ divides $a$ in $R$, which shows that $p$ is prime in $R$, a contradiction. By assumption, there is $s \in S$ and $q \in R$, such that $sa = pq$. Since $p$ is irreducible in $R$ and does not belong to $S$, every prime factor of $s$ divides $q$. Write $s = p_1^{\alpha_1} \cdots p_n^{\alpha_n}$ with $p_i$ prime in $R$ and $\alpha_i > 0$ for every $i$. By an obvious induction on $\sum_i \alpha_i$, we deduce that $s$ divides $q$. Therefore $p$ divides $a$, as claimed. Consider now a prime ideal $\mathfrak{p}$ of $R$ of height one such that $D\mathfrak{p}$ is a principal ideal of $D$. If $\mathfrak{p} \cap S = \emptyset$, then the ideal $D\mathfrak{p}$ is prime in $D$ [1, Theorem 4.1.$ii$] and any element $p \in R$ such that $D\mathfrak{p} = Dp$ is a non-zero prime element of $D$, which is impossible by the first part. Therefore $\mathfrak{p}$ contains an element of $S$, and hence contains a non-zero prime element of $R$. Because $\mathfrak{p}$ has height one by hypothesis, we can conclude that $\mathfrak{p}$ is generated by a single prime element.
We are now in position to prove the above claim.
Proof of the Claim. Thanks to the above Lemma, we only need to address the assertion about class groups. The map $\mathfrak{p} \mapsto D\mathfrak{p}$ defined on the primes ideals of $R$ induces a surjective group homomorphism from $\operatorname{Cl}(R)$ onto $\operatorname{Cl}(D)$ by [1, Theorem 4.1.$(ii)$]. Thus $\operatorname{Cl}(D)$ is trivial if $\operatorname{Cl}(D)$ is trivial. Let us assume now that $\operatorname{Cl}(R)$ is not trivial. Since the classes of the prime ideals of $R$ generate $\operatorname{Cl}(R)$, there is a non-principal prime ideal $\mathfrak{p}$ in $R$. By the above Lemma, we know that $D\mathfrak{p}$ is not principal in $D$, i.e., it defines a non-trivial element of $\operatorname{Cl}(D)$.
Note 1. This MSE post provides us with a Dedekind domain with no non-zero prime elements, namely the affine domain $D = \mathbb{C}[x, y]/ (y^2 - x^3 - x)$. If $R$ is the affine ring of a non-singular curve over an algebraic closed field, the Picard group of $R$ is finite if and only if the curve is rational (quote from D. Eisenbud's Section 11.4). This implies that $\operatorname{Cl}(D)$ is infinite.
Note 2. The above Claim originates from this MSE answer, but the proof was initially incorrect. (It is fixed now).
Note 3. Here is a reference for the classical number theoretic result mentioned by the OP. Let $R$ be a Dedekind domain of arithmetical type. Then every ideal class of $R$ is represented by infinitely many prime ideals of $R$ by [2, Theorem VII.13.2 (Dirichlet density theorem)]. The density of the set of prime ideals in any given ideal class is $\frac{1}{h}$ where $h = \vert \operatorname{Cl}(R) \vert$ is the class number of $R$.
Here is a very different sort of example. Let $X$ be a smooth projective curve of genus $\geq 2$ over an algebraically closed field $k$, let $x$ be a single point of $X$, and let $A$ be the coordinate ring of $X \setminus \{ x \}$. Concretely, we're talking about something like $k[x,y]/(y^2 - f(x))$ where $f(x) \in k[x]$ is a squarefree polynomial of degree $2g+1$ and the characteristic of $k$ is not $2$.
Let $J$ be the Jacobian variety of $X$. Then the class group of $X$ is $J(k)$, but the primes of $A$ correspond to the embedding of $(X \setminus \{ x \})(k)$ into $J(k)$. For $g \geq 2$, we have $\dim J = g > \dim X = 1$, so almost all points in $J(k)$ are not in the image of $X(k)$.
I bet you can make examples with curves over $\mathbb{Q}$ as well, but I'll leave that to the number theorists.
