An illusionist and their assistant are about to perform the following magic trick

NOTE: I found counterexamples to the explicit $f$ I initially posted. I removed it but am leaving the rest of the answer up as a partial solution.

Notation and Remarks

Let $S_n$ denote the set of permutations of length $n$ and let $C_{n,k}$ be the set of covered permutations. For example, the permutation $12345678 in S_8$ and $123cdotcdotcdot78 in C_{8,3}$. For brevity I often drop the subscripts.

The act of covering gives us a relation $sim$ between the two sets, i.e. we say that $pi in S$ and $c in C$ are compatible if $c$ is a covering of $pi$. We can visualize this compatibility relation as a bipartite graph. For $k=2$ and $n=3$ we have:

$ qquad qquad qquad qquad qquad qquad $

We need to find an injective function $f : S_n rightarrow C_{n,k}$ such that $pi$ and $f(pi)$ are always compatible. The assistant performs the function $f$ and the illusionist performs the inverse $f^{-1}$. As per the problem requirements, both $f$ and $f^{-1}$ need to be computable in poly(n) time for a given input. We note that given such an $f$, computing $f^{-1}$ is straightforward: given a covering $c$, we consider the compatible permutations. Among these, we choose the $pi$ such that $f(pi) = c$.

For $n = k! + k - 1$ we note that $|S_n| = |C_{n,k}| = n!,$. We also note that each permutation is compatible with exactly $k!$ coverings and each covering is compatible with exactly $k!$ permutations. As OP mentioned, the Hall marriage theorem thus implies that a solution exists. We can find such a solution using a maximum matching algorithm on the bipartite graph. This is how @orlp found a solution for $k=3$ in the comments. However, the maximum matching algorithm computes $f$ for every permutation in poly(n!) time, where we instead need to compute $f$ for a single permutation in poly(n) time.

This is a strategy that works in every case I checked, but its validity for all k needs to be proved. By his choice of placing the scarf, the assistant conveys information to the illusionist. There are $k!$ ways of placing the scarf, to the assistant.

Consider a random permutation ($a_1,a_2,...,a_n$) of {$1,2,...,n$}, that the audience chooses. The assistant looks at this arrangement and assigns a parity to it as follows:

1. He takes the $k$-touple ($a_1,a_2,...,a_{k}$). He constructs a $k$-digit number (concatenation) from it as $$a_1a_2...a_{k}$$ He then calculates the rank of this number among all of its $k!$ permutations (lowest number gets rank 0 and highest gets rank $(k!-1)$). He assigns it a variable $$boxed{x_1=(rank)}$$

2. Assign $x_2$ to {$a_2,a_3,...,a_{k+1}$}. Similarly assign $x_3,x_4,...,$ and $x_{k!}$. Take that $a_i=a_{i+n}$

Compute the parity: $$p=modleft(sum_{i=1}^{k!} x_i,k!right)$$

There are $k!$ values of $p$ possible: {$0,1,2,...,k!-1$}. Depending on the value of $p$ the assistant chooses where to place the scarf. (When $p=0$ he places over first $k!$ balls. When $p=1$ he places over second $k!$ balls,.. etc)

When the illusionist sees the obscured arrangement, he knows the value of $p$ by the position of the scarf. Although I haven't proved it yet, only one arrangement of the obscured balls gives this value of $p$. This strategy works for all cases of $k=2$ and many cases of $k=3$. But it is a behemoth to prove for general $(k,n)$.