Rubik Cube Algorithm for general n
Algorithms for Solving Rubik's Cubes by Demaine et al. shows that an $n\times n\times n$ Rubik's Cube can be solved in $O(\frac{n}{\log n})$ moves and this is (asymptotically) optimal.

I am not certain on the complexity of actually computing such a solution but I suspect that (by closely following the steps in the proof) it can be done in polynomial time (probably $O(n^2)$ or $O(n^2\log n)$).

There likely isn't anything out there on higher-dimensional cubes. If there was, they would certainly have cited the Demaine paper. There is a trivial way to solve a $n\times n\times n$, since there exist move sequences that solve an individual cubie in $O(1)$ time. Therefore, if such sequences also exist for higher-dimensional cubes, they could be solved in $O(n^{d-1})$ steps since that is how many cubies are on the surface. And perhaps by extending Demaine's technique you could get that down to $O(\frac{n^{d-1}}{\log n})$ by solving multiple ($O(\log n)$) cubies in one go.

You might be able to find more information here: http://www.superliminal.com/cube/solution/solution.htm