(I asked a very concise version of this one month ago on cs.stackexchange,
and although it got edited, it was not (otherwise) responded to.)
In this post, for positive integer values $k$, "$k$-Sokoban" is simply short for
"the problem "Given an instance of Sokoban with at most $k$ boxes, is that instance solvable?"".
For any particular encoding, that is one problem for which complexities should be expressed
in terms of both $k$ and $n$ (like how the complexity of graph algorithms is frequently
expressed in terms of both $|V\hspace{.02 in}|$ and $|\hspace{.02 in}E\hspace{.03 in}|\hspace{-0.02 in}$), rather than a different problem for each value of $k$.
(Since one could just add inaccessible squares with a box already at its storage location,
"at most" can be replaced with "exactly" as long as $n$ can be increased sufficiently.)
This post has one part on upper bounds for the hardness of $k$-Sokoban,
one part on lower bounds for the hardness of $k$-Sokoban, and
one part on the plausibility of $k$-Sokoban being in a specific class.
Although these questions are complicated, that is just to expand the space of
possible answers to them. $\:$ I could simplify them, but that would make them harder.
By this paper, standard Sokoban can "easily" (i.e., via conversions of low complexity) emulate a non-deterministic LBA with the size increase and slowdown factors bounded by a polynomial
in the number of states per cell. $\:$ (The three places on pages 7 and 9 where it says "Select Next State" show the non-deterministic part, even thought the paper doesn't explicitly claim that.)
On the other hand, instances of $k$-Sokoban with size $n$ have $n^{\hspace{.02 in}O\hspace{.02 in}(k)}$ possible states and
one can easily work with those states, so $k$-Sokoban is in NSPACE$[\hspace{-0.02 in}O\hspace{.02 in}(k\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n))] \;$.
Note that any way to solve $O(k)$-Sokoban with just resources of somewhat standard types
that are not known to be able to decide all of $\:\operatorname{NSPACE}\hspace{.02 in}[k\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n)]\:$
would constitute an obstruction in the sense of my upper bound question.
As a broad example of that, I'm not aware of any way to show that for each
positive real number $\epsilon$, each (parameterized) language in $\:\operatorname{NSPACE}[\hspace{-0.02 in}O\hspace{.02 in}(k\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n))]$
can infinitely-often be decided by the version of $\;$S$_{\hspace{.02 in}2}$nonuniformTISP$\left[n^{\hspace{.02 in}k^2\hspace{-0.02 in}\cdot o(\log(n))}\hspace{-0.05 in},\hspace{-0.02 in}n^{\hspace{.02 in}o(k)}\hspace{-0.04 in}\right]$
in which [whichever of $y,\hspace{-0.02 in}z$ is required to exist] can be chosen to have length $n^{\hspace{.02 in}o(k)}\hspace{-0.04 in}$
but the referee has (read-only) random access to $\:2^{\lceil n\text{^}\epsilon \hspace{-0.02 in}\rceil}\:$ bits of advice.
The Upper Bound Question:
Is there any obstruction to $O(k)$-Sokoban with size $poly(n)$ being "easily"
(i.e., via conversions of low complexity) able to emulate non-deterministic
Turing machines with $\:k\hspace{-0.04 in}\cdot \hspace{-0.04 in}\log(n)\:$ bits of workspace such that the size increase and
slowdown factors are still bounded by a polynomial in the number of states per cell?
(Other sorts of "obstruction"s would be the existence of such emulation procedures implying
a containment or non-containment or that a problem does or doesn't reduce to its complement,
where there is no known way to show the right-hand-side of the implication unconditionally.
Essentially, such an obstruction could be any argument for why it should be
difficult to prove the existence of such emulation procedures that is significantly
better than "$k$-Sokoban does not appear to support suitable gadgets".)
Let "MiTCGG" be short for "the problem "Is there a matching from one given set of $k$ vertices
to another given set of $k$ vertices in the transitive closure of the given directed grid graph?"".
(Those letters stand for "Matching in the Transitive Closure of a Grid Graph".) $\:$ Since the region
X X
X XX XX
X X X
XX X
XXX
has neither boxes nor storage locations and is such that a box can be pushed from the top
to exit out the bottom but can't be pushed from the bottom to the top, MiTCGG can easily
be reduced to $k$-Sokoban. $\;\;\;$ By this paper, the $\: k=1 \:$ version of MiTCGG is hard for NC1.
Additionally, the nLBA emulation result for standard Sokoban that I cited
earlier in this post will give useful lower bounds when $k$ is large enough.
Thus, $1$-Sokoban (so in particular $k$-Sokoban) is NC1-hard and instances of $O(k)$-Sokoban
with size $O(k)$ can "easily" (i.e., via conversions of low complexity) emulate NSPACE(k).
The Lower Bound Question:
Are there any hardness results for the search version of $k$-Sokoban
which do not automatically follow from the hardness results
everything in NC1 $\: \leq \:$ directed Grid Graph reachability $\: \leq \:$ MiTCGG $\: \leq \:$ $k$-Sokoban
and the fact that instances of $O(k)$-Sokoban with size $O(k)$ can
"easily" (i.e., via conversions of low complexity) emulate NSPACE(k)?
A 2-worktape non-deterministic Turing machine can solve MiTCGG in a way that uses
at most $O(\log(n))$ bits on one work tape and at most $k$ bits on the other work tape.
(Sketch: iterate over the $k$ starting points in order, guess directed paths to currently
unused finishing points, and keep track of which finishing points have been used so far.)
The Class Membership Question:
Is there any obstruction to $k$-Sokoban being solvable by a 2-worktape
non-deterministic Turing machine that uses $\:O\hspace{.02 in}(\log(n))\:$ bits
on one work tape and at most $k$ bits on the other work tape?
