@Ashot: Finitely presented examples exist. It is in our paper with Olshanskii, Olshanskii, A. Yu.; Sapir, M. V., Length functions on subgroups in finitely presented groups. Groups—Korea '98 (Pusan), 297–304, de Gruyter, Berlin, 2000.
An easier construction is this. Take the free Abelian group $A$ with generators $x_i, i=0,1,...$. Consider an injective recursive function $\mathbb{N}\to \mathbb{N}$ with non-recursive image $f(n)$.
Impose the following relations on $A$:
$x_{f(n)}=x_0^{n!}, n=1,2,...$. The word problem in the resulting (infinitely generated) group $A_f$ is solvable. Indeed, consider any word $w=x_{i_1}^{k_1}...x_{i_m}^{k_m}$, $i_1\lt i_2\lt...$. That word is equal to 1 if and only if each $i_s$ is of the form $f(n_s)$ for some $n$ and $k_1n_1!+k_2n_2!+...=0$. That means all $n_i$ cannot be much bigger than $\max |k_i|$. Thus checking $w=1$ requires finite number of calculations of the function $f(n)$, so it is decidable. On the other hand the membership problem of $x_m$ into $\langle x_0\rangle$ is clearly undecidable since $f$ has non-recursive image.
Now use Clapham's version of Higman's embedding and embed $A_f$ into a finitely presented group $G$ with decidable word problem. Given $i$, one can recursively find a word in $G$ representing $x_i$. Thus the membership problem in the cyclic subgroup $\langle x_0\rangle$ of $G$ is undecidable.
Update Here is how to construct an injective recursive function with non-recursive image. Using Matiyasevich's theorem, find a polynomial $p(x_1,...,x_s)$ such that the solvability of the equation
$a=p(x_1,...,x_s)$ is undecidable. Now take any Turing machine $M$ that computes $p(x_1,...,x_n)$ in binary. Add a new tape to $M$ and during the computation of $M$ write down the history of computation (i.e. numbers of the executed commands in binary, separated by number 3) on the new tape. When the machine stops, interpret the word written on the extra tape and the value of $p(x_1,...,x_s)$ as one number $f(x_1,...,x_s)$ (say, write first the value of $p$, then number 4, then the history, view the whole number as written in the 5-ary system). The function $n$ is clearly recursive and injective because the history determines the values of $x_1,...,x_s$ (make the machine scan the input before it computes $p$). It is also clear that the image of $n$ is not recursive. To make $n$ a function in one variable, precompose it with a (Goedel) function that enumerates ${\mathbb Z}^s$.
