The answer appears to be similar to one that I asked on cstheory.SE about Discrete log in GL(2,p) (i.e., given $A,B$, find $k$ such that $A^k=B$). In this question we are given less information, but similar techniques should still apply.
Start by putting $A$ into Jordan normal form, i.e., write $A=PJP^{-1}$ where $J$ is the Jordan normal form and $P$ is a suitably chosen invertible matrix. Then $A^k = PJ^k P^{-1}$, so without loss of generality I only need to consider possibilities for $A$ that are already in Jordan normal form. This means that $A$ can be expressed as a concatenation of Jordan blocks:
$$A = \begin{pmatrix} J_1 \\&\ddots\\ &&J_n\end{pmatrix}.$$
Each Jordan block gives us an independent system of equations, so let me look at a single Jordan block at a time. We can break this down into cases, based upon the size of the Jordan block $J$:
A size-1 Jordan block. Suppose $J$ is a $1\times 1$ Jordan block, i.e.,
$$J=\begin{pmatrix} \lambda \end{pmatrix}.$$
Then it is easy to see that the problem is exactly as hard as the discrete log to base $\lambda$ (unless $x=0$ in this component, in which case it is unsolvable for information-theoretic reasons).
A size-2 Jordan block. Suppose $J$ is a $2\times 2$ Jordan block, i.e.,
$$J = \begin{pmatrix} \lambda &1\\ 0 &\lambda \end{pmatrix}$$
where $\lambda \ne 0$. A simple induction shows that
$$J^k = \begin{pmatrix} \lambda^k &k\lambda^{k-1}\\ 0 &\lambda^k \end{pmatrix}.$$
Let $P^{-1}x=(x_1, x_2)$ and $P^{-1}y=(y_1, y_2)$. Then we obtain the linear equations
\begin{align*}
\lambda^k x_1 + k\lambda^{k-1} x_2 &= y_1\\
\lambda^k x_2 &= y_2
\end{align*}
which has the solution
$$k = \lambda (y_1 - x_1 y_2/x_2)/y_2.$$
We see that as long as $x_2 \ne 0$, the problem is easy and we can solve for $k$ with a little bit of arithmetic (no discrete log needed). If $x_2=0$, I'd conjecture that this case is hard.
A larger Jordan block. If we have a larger Jordan block, say $m \times m$, basically the same thing happens. The top row of $J^k$ is $(\lambda^k, k \lambda^{k-1}, {k \choose 2} \lambda^{k-2}, \dots)$, and each subsequent row is a right-shift of the one before it. Then, as long as $(x_2,x_3,\dots,x_m) \ne (0,0,\dots,0)$, we can solve for $k$ easily as in the $2\times 2$ case.
So, each Jordan block gives us a chance to solve for $k$. If any of the Jordan blocks are easy, we learn $k$. If all of the Jordan blocks are hard, learning $k$ is hard.
In summary: If the Jordan normal form of $A$ is diagonal, and at least one of the diagonal elements is such that discrete log to that base is hard, then this problem is as hard as the discrete log. On the other hand, if the Jordan normal form is not diagonal---i.e., if it has at least one Jordan block of size $>1$---then the problem is easy (except in corner cases where the wrong components of $x$ happens to be zero).
