#JavaScript (ES7),  77  72 bytes

Takes input as a list of digits.

f=(a,k)=>([...[k*k]+k**3].sort()+'').match(a.sort().join`.*`)?k:f(a,-~k)

Try it online!

###Commented

f = (                     // f is a recursive function taking:
  a,                      //   a[] = input
  k                       //   k   = counter, initially undefined
) =>                      //
  ( [...[k * k] + k ** 3] // concatenate k² and k³ and split the resulting string
    .sort()               // sort from lowest to highest digit
    + ''                  // coerce back to a string (this puts commas between the
                          // digits, but they are harmless)
  ).match(                // test whether it matches:
    a.sort()              //   the input list sorted the same way  
    .join`.*`             //   joined with .* patterns, so that unused digits and
                          //   commas are ignored
  ) ?                     // if it does:
    k                     //   stop recursion and return k
  :                       // else:
    f(a, -~k)             //   try again with k + 1

JavaScript (ES7),  77  72 bytes

Takes input as a list of digits.

f=(a,k)=>([...[k*k]+k**3].sort()+'').match(a.sort().join`.*`)?k:f(a,-~k)

Try it online!

Commented

f = (                     // f is a recursive function taking:
  a,                      //   a[] = input
  k                       //   k   = counter, initially undefined
) =>                      //
  ( [...[k * k] + k ** 3] // concatenate k² and k³ and split the resulting string
    .sort()               // sort from lowest to highest digit
    + ''                  // coerce back to a string (this puts commas between the
                          // digits, but they are harmless)
  ).match(                // test whether it matches:
    a.sort()              //   the input list sorted the same way  
    .join`.*`             //   joined with .* patterns, so that unused digits and
                          //   commas are ignored
  ) ?                     // if it does:
    k                     //   stop recursion and return k
  :                       // else:
    f(a, -~k)             //   try again with k + 1

#JavaScript (ES7), 77 bytes

Takes input as a string.

f=(n,k)=>([...[k*k]+k**3].sort()+'').match([...n].sort().join`.*`)?k:f(n,-~k)

Try it online!

Or 72 bytes if we can take input as an array of integers.

f = (                     // f is a recursive function taking:
  n,                      //   n = input
  k                       //   k = counter, initially undefined
) =>                      //
  ( [...[k * k] + k ** 3] // concatenate k² and k³ and split the resulting string
    .sort()               // sort from lowest to highest digit
    + ''                  // coerce back to a string (this puts commas between the
                          // digits, but they are harmless)
  ).match(                // test whether it matches:
    [...n]                //   the input split into digits
    .sort()               //   sorted the same way
    .join`.*`             //   joined with .* patterns, so that unused digits and
                          //   commas are ignored
  ) ?                     // if it does:
    k                     //   stop recursion and return k
  :                       // else:
    f(n, -~k)             //   try again with k + 1

#JavaScript (ES7),  77  72 bytes

Takes input as a list of digits.

f=(a,k)=>([...[k*k]+k**3].sort()+'').match(a.sort().join`.*`)?k:f(a,-~k)

Try it online!

f = (                     // f is a recursive function taking:
  a,                      //   a[] = input
  k                       //   k   = counter, initially undefined
) =>                      //
  ( [...[k * k] + k ** 3] // concatenate k² and k³ and split the resulting string
    .sort()               // sort from lowest to highest digit
    + ''                  // coerce back to a string (this puts commas between the
                          // digits, but they are harmless)
  ).match(                // test whether it matches:
    a.sort()              //   the input list sorted the same way  
    .join`.*`             //   joined with .* patterns, so that unused digits and
                          //   commas are ignored
  ) ?                     // if it does:
    k                     //   stop recursion and return k
  :                       // else:
    f(a, -~k)             //   try again with k + 1

#JavaScript (ES7), 77 bytes

Takes input as a string.

f=(n,k)=>([...[k*k]+k**3].sort()+'').match([...n].sort().join`.*`)?k:f(n,-~k)

Try it online!

###Commented

f = (                     // f is a recursive function taking:
  n,                      //   n = input
  k                       //   k = counter, initially undefined
) =>                      //
  ( [...[k * k] + k ** 3] // concatenate k² and k³ and split the resulting string
    .sort()               // sort from lowest to highest digit
    + ''                  // coerce back to a string (this puts commas between the
                          // digits, but they are harmless)
  ).match(                // test whether it matches:
    [...n]                //   the input split into digits
    .sort()               //   sorted the same way
    .join`.*`             //   joined with .* patterns, so that unused digits and
                          //   commas are ignored
  ) ?                     // if it does:
    k                     //   stop recursion and return k
  :                       // else:
    f(n, -~k)             //   try again with k + 1

#JavaScript (ES7), 77 bytes

Takes input as a string.

f=(n,k)=>([...[k*k]+k**3].sort()+'').match([...n].sort().join`.*`)?k:f(n,-~k)

Try it online!

Or 72 bytes if we can take input as an array of integers.

###Commented

f = (                     // f is a recursive function taking:
  n,                      //   n = input
  k                       //   k = counter, initially undefined
) =>                      //
  ( [...[k * k] + k ** 3] // concatenate k² and k³ and split the resulting string
    .sort()               // sort from lowest to highest digit
    + ''                  // coerce back to a string (this puts commas between the
                          // digits, but they are harmless)
  ).match(                // test whether it matches:
    [...n]                //   the input split into digits
    .sort()               //   sorted the same way
    .join`.*`             //   joined with .* patterns, so that unused digits and
                          //   commas are ignored
  ) ?                     // if it does:
    k                     //   stop recursion and return k
  :                       // else:
    f(n, -~k)             //   try again with k + 1