The only known way to construct this example (say, in the case of groups, the case of semigroups is similar) is the following. First consider the free Abelian group $F$ with free generators $a_1,a_2,...$. Pick a recursively enumerable non-recursive set $I$ and impose relations $a_n^{m!}=1$ if $n$ is the $m$th number from $I$ (we assume that there exists a computer that lists numbers in $I$ in some order one by one). That group, call it $A$, has solvable word problem. Indeed, consider any word $w=a_{i_1}^{k_1}\ldots a_{i_s}^{k_s}.$ That word is equal to 1 in $A$ iff each $k_i$ is divisible by $m!$ such that $a_i$ is the $m$-th number in $I$. That gives restriction to $m$. So given $w$ we start the computer that lists $I$ and wait till we have the first (not in the natural order!) $k_1+...+k_s$ numbers from $I$ listed. The power problem in $A$ is not decidable of course. Since $A$ has solvable word problem, by Higman's theorem, it embeds into a finitely presented group $G$. By Clapham's theorem, we can assume that $G$ has decidable word problem. But the power (order) problem in $G$ is not decidable.
There are no examples which are given by very few defining relations. The reason is that the solvability of the order problem is not easy to achieve without Higman embedding (I do not know any such way without getting undecidable word problem also) which is very implicit.