It seems relatively easy to construct such a bundle by induction. Namely:

**Step 0** If $r=1$, there are clearly line bundles of given degree $d$ on $X$, since $k$ is assumed to be algebraically closed.

**Step 1** Choose $(r',d')$ such that $0<r'<r$, $d'/r'>d/r$, and there are no integral points within (or on the edges) of the triangle with vertices $(0,0)$, $(r',d')$, and $(r,d)$. For instance, can take $(r',d')$ satisfying the first two inequalities whose distance from the line through $(0,0)$ and $(r,d)$ is minimal.

**Step 2** The condition that there are no integral points on the boundary of the triangle implies that $gcd(r',d')=gcd(r-r',d-d')=1$. Let $E_1$ and $E_2$ be stable bundles such that $rk(E_1)=r'$, $deg(E_1)=d'$, $rk(E_2)=r-r'$, $deg(E_2)=d-d'$, which exist by the induction hypothesis. Choose a non-trivial extension
$$0\to E_2\to E\to E_1\to 0,$$
which exists by the Riemann-Roch Theorem (here we need that the genus of $X$ is at least one).

**Step 3** It is easy to see that $E$ is stable. Indeed, assume it is not, and $F\subset E$ is destabilizing. Then the slope of $F$ is at most $d'/r'$, and dually the slope of $E/F$ is at least $(d-d')/(r-r')$. From the condition that there are no integral points in the triangle, we see that $rk(F)=r'$ and $deg(F)=d'$. Because of stability of $E_1$ and $E_2$, this implies that the map $F\to E\to E_1$ is an isomorphism, which would split the exact sequence for $E$. Contradiction.

**Remark** The only place where we need the field to be algebraically closed is Step 0. So as long as you know that line bundles of every degree exist on $X$, the statement holds. For instance, it works if $X$ has a $k$-point, or if the base field is finite (see this question), but fails if the field is $\mathbb{R}$.