Find All Permutations of String in Scala
The code looks to be correct, yes, the testing looks good too.  I was
thinking whether List(List()) for the input List() makes sense, but
it seems like that's a sensible output.
For the code readability I'd rename str, especially since it's not
really a string, but a list.  The complicated match expression in
permutations can just be simplified to case _ and in the body the
original argument can be reused again.
I'd also inline shifteds value since it's just a single call and the
name doesn't really tell me anything.  On that note, docstrings for the
functions might be a nice touch, especially for the shift and shiftN
methods.
The unused case labels can also just be _ everywhere.  Depends of
course, for me this makes it clearer that really there's always just two
cases, either matching an empty list, or a non-empty one, there's no
third case.
Would look like this then:
object Permutations {
  def permutations[A](list: List[A]): List[List[A]] =
    list match {
      case Nil =&gt; List(Nil)
      case _ =&gt;
        shiftN(list, list.length).flatMap {
          case head :: tail =&gt;
            permutations(tail).map(head :: _)
          case _ =&gt; Nil
        }
    }

  def shiftN[A](list: List[A], n: Int): List[List[A]] = {
    if (n &lt;= 0) Nil
    else {
      val shifted: List[A] = shift(list)
      shifted :: shiftN(shifted, n - 1)
    }
  }

  def shift[A](list: List[A]): List[A] = list match {
    case head :: tail =&gt; tail ++ List(head)
    case _ =&gt; Nil
  }
}

Lastly, performance-wise it depends what your constraints are: For
List input and List output, restricting it to single linked lists,
this is fine, though I haven't benchmarked them of
course.  Potentially converting the shifted :: shiftN(...) call into
using an accumulator might be worth a bit, instead of having a deep call
stack, but again, it'll probably only matter for longer inputs.
But there are way quicker algorithms, though you might want to copy the
input into a vector that can be accessed in constant time for each
index.  (I found the
QuickPerm algorithm, as explained here
absolutely straightforward to implement from scratch.)