For $n>k$ the sum is equal to $(2^k-1)n -2^{k-1}k$ (by the binomial theorem) so Mathematica's asymptotic expansion isn't very helpful.

It seems unlikely, but it would be difficult to prove that there is no such transformation.

You can consider the problem of counting hypergraphs on n vertices with specified degrees of the vertices as counting partitions of a multiset in which each block is a set. Some references for this problem can be found in my paper Symmetric Functions and P-Recursiveness, J. Combin. Theory Ser. A 53 (1990), 257–285, people.brandeis.edu/~gessel/homepage/papers/dfin.pdf

Very nice proof!

The sum in question is $n!^p$ times the coefficient of $x^n$ in $$\biggl(\sum_{j=0}^\infty \frac{x^j}{j!^p}\biggr)^s,$$ so the techniques of Section VII of Flajolet and Sedgewick's Analytic Combinatorics (algo.inria.fr/flajolet/Publications/book.pdf) might be helpful.

Don't forget that Wilf is also a co-author of A=B.

As I recall, this problem is discussed in Riordan's Introduction to Combinatorial Analysis, but I don't have my copy handy. You might also be able to find some relevant references by searching for "discordant permutations". On another aspect of the question, although the number of possible $\tau$ depends on $\sigma$, this number is close to $n!/e^2$ independently of $\sigma$. Stronger asymptotic results on the number of ways to add a row to a Latin rectangle can be found in C. D. Godsil, and B. D. McKay, Asymptotic enumeration of Latin rectangles. J. Combin. Theory Ser. B 48 (1990), 19–44.