This problem can be solved using the baby step, giant step algorithm which uses the meet in the middle trick.
We can write k = $i sqrt(n) + j$

Notice that i <= sqrt(n) and j <= sqrt(n).
Now our equality looks like this p^ (i ([sqrt(n)] + 1) + j) = q modulo n. We can divide by p^j and get p^(i[sqrt(n)] + 1) = qp^-j modulo n.

Notice that $i <= sqrt(n)$ and $j <= sqrt(n)$.
Now our equality looks like this $p^(i ([sqrt(n)] + 1) + j)^ = q modulo n$.
We can divide by $p^j^$ and get $p^(i[sqrt(n)] + 1)^ = qp^-j^ modulo n$.

Now the application of meet in the middle becomes obvious. We can brute force through the numbers on each side of the equality and find a match.
The algorithm takes O(sqrt(n)) space and O(sqrt(n)) time.