Not an answer, but maybe a start:

It is fairly clear why trivial cases like $n=18,$ power$=2$ don't work, after all of the sum-pairs $\neq$ a power of $2$ that are $\leq2n$ are stripped away:

<img src="https://i.sstatic.net/h6zHK.png" width="500" height="120">

Complete cycles are much easier to search for: `cycleP[33, 2]` *(for $n=33,$ power$=2$, code below)* produces

<img src="https://i.sstatic.net/HFJk0.png" width="500" height="250">

whereas `cyclePall[23, 2]` produces

<img src="https://i.sstatic.net/AMlHQ.png" width="320" height="150">
<img src="https://i.sstatic.net/qBybd.png" width="320" height="150">
<img src="https://i.sstatic.net/HcLRq.png" width="320" height="150">

and it is clear why nothing below $300$ish will work for power $3$ by just looking at dangling nodes of $n=200,$ power$=3$:

![enter image description here][1]

-----------------

    cycleP[n_, pow_] := 
    With[{graph = Graph[DeleteDuplicates[Flatten[Thread[#[[1]] -> #[[2]]] & /@ 
    Transpose[{Range@n, Table[If[#[[1]] == hh, #[[2]], #[[1]]] & /@ 
    Select[Flatten[DeleteCases[Table[With[{aa = Transpose@{(ConstantArray[#, #]
    &@nn - Range@nn), Reverse@(ConstantArray[#, #] &@nn - Range@nn)}}, 
    Select[Rest@ Take[aa, Floor[Length@aa/2]], #[[1]] <= n && #[[2]] <= n &]], 
    {nn, Range[2, Floor[(2 n)^(1/pow)]]^pow + 1}], {}], 1], #[[1]] == hh \[Or] #[[2]] 
    == hh &], {hh, n}]}]], Sort[#1] == Sort[#2] &], DirectedEdges -> False, 
    VertexLabels -> "Name"]}, Column[{Show[#, ImageSize -> 400] &@
    HighlightGraph[graph, Style[FindCycle[graph, {n}], {Darker@Red, Thick}]], 
    Flatten@(#[[All, 1]] & /@ FindCycle[graph, {n}])}]]

    cyclePall[n_, pow_] := 
    With[{cc = DeleteDuplicates[Flatten[Thread[#[[1]] -> #[[2]]] & /@ 
    Transpose[{Range@n, Table[If[#[[1]] == hh, #[[2]], #[[1]]] & /@ 
    Select[Flatten[DeleteCases[Table[With[{aa = Transpose@{(ConstantArray[#, #] &@nn - 
    Range@nn), Reverse@(ConstantArray[#, #] &@nn - Range@nn)}}, 
    Select[Rest@ Take[aa, Floor[Length@aa/2]], #[[1]] <= n && #[[2]] <= 
    n &]], {nn, Range[2, Floor[(2 n)^(1/pow)]]^pow + 1}], {}], 1], #[[1]] == hh \[Or] 
    #[[2]] == hh &], {hh, n}]}]], Sort[#1] == Sort[#2] &]}, With[{dd = 
    Split@Sort@Join[cc[[All, 1]], cc[[All, 2]]]},
    With[{jj = DeleteCases[Flatten@(If[Length@# == First@Sort[Length@# & /@ dd], #, 0] 
    & /@ dd), 0]}, With[{ll = Flatten@Table[Thread[#[[1]] -> #[[2]]] & /@ 
    Transpose@{ConstantArray[jj[[kk]], n], Range@n}, {kk, Length@jj}]},
    With[{zz = Table[Join[{ll[[vv]]}, cc], {vv, Length@ll}]}, With[{zzz = 
    DeleteCases[Table[FindCycle[Graph[zz[[ww]], DirectedEdges -> False, 
    VertexLabels -> "Name"], {n}], {ww, Length@zz}], {}]}, With[{graphs = 
    (HighlightGraph[Graph[cc, DirectedEdges -> False, VertexLabels -> "Name"], 
    Style[#, {Darker@Red, Thick}]] & /@ zzz)},Column[{If[Length@graphs == 0, 
    Show[Graph[cc, DirectedEdges -> False, VertexLabels -> "Name"], ImageSize -> 400], 
    Show[#, ImageSize -> 400] & /@ graphs],#[[All, 1]] & /@ (Rest@# & /@
    Flatten[zzz, 1])}]]]]]]]]

*(Mathematica 10 only)*

#Update#

This is a placeholder, as I have no access to my computer for a few days, but outlines rough sketch of idea:

Illustrated as a clock with $1$ at the top for $n=24$ power$=2,$ this is a far more systematic way to think about it:

![enter image description here][2]

grouping sum-pairs by square $\leq 48.$ The superimposition shows all possible paths with one remaining odd "leg". There is therefore [no Eulerian circuit (or trail)][3] for $n=24$ power$=2.$

As long as there is ***at least*** two adjoining points for all but $2$ points, there will be an Eulerian trail. If ***all*** points have at least two adjoining points, it is likely there will be an Eulerian circuit.

It is highly likely then, that over a certain $n$ for each power will guarantee at least one Eulerian trail.

  [1]: https://i.sstatic.net/OvukW.png
  [2]: https://i.sstatic.net/QY1HK.png
  [3]: http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg