Techniques/tools for constructing hard instances of a puzzle game
As I understand it, the problem you are interested in is Bounded PlanSAT which asks whether there is a solution of length $k$ or less. PlanSAT on the other hand asks whether there exists any plan than solves the problem. Bounded PlanSAT is, for example, decidable even if we add function symbols to our language and thus make the number of states infinite. Both of these decision problems are indeed in $\text{PSPACE}$.

As for your problem of generating hard instances (meaning long solutions), one approach could be GRAPHPLAN which uses a data structure called the planning graph. Now, the planning problem asks if we can reach a goal state $G$ from the initial state $S_0$. Suppose we are given a tree of all possible actions from the initial state to successor states, and their successors, and so on. Indexed appropriately, we could answer the question of "is $G$ reachable from $S_0$?" just by looking it up. This is naturally impractical, since the tree is of exponential size. The planning graph is a polynomial-size approximation to this tree that can be constructed quickly. 

The planning graph can't answer for sure whether $G$ is reachable from $S_0$, but it can estimate how many steps it takes to reach $G$. The estimate is always correct when it reports $G$ is not reachable, and it never overestimates the number of steps. Hence it is an admissible heuristic.

I agree this is perhaps not exactly what you are looking for. Nevertheless this way, one does not have to actually solve the instance. I don't think solve time is a particularly useful measure of hardness. For some solvers, some instances are easy. For some solvers, they are hard. In this sense, something like long solutions seem like a good measure of hardness.

Another thing that crossed my mind was the fact that classical planning can be represented as a constraint problem (SAT/CSP, see for example SATPLAN). If translated as SAT for example, one can use all the tools available in that domain. You might be interested for example in the question Measuring the difficulty of SAT instances. As for directly generating an instance of planning that has a solution of length more than $k$, I don't know the answer to.

By the way, if you want to solve instances in practice, Helmert (2001) analyzes many classes of planning problems and notes that constraint-based approaches such as GRAPHPLAN and SATPLAN are best for $\text{NP}$-hard domains while search-based approaches do better in domains where feasible solutions can be found without backtracking. Both have problems in domains with many objects because they must create many actions. One can also check out the International Planning Competition (IPC), similar to the SAT competition(s).