We generalize the concept of partial permutations of Ivanov and Kerov and introduce $k$-partial permutations. This allows us to show that the structure coefficients of the center of the wreath product $\mathcal{S}_k\wr \mathcal{S}_n$ algebra are polynomials in $n$ with non-negative integer coefficients. We use a universal algebra $\mathcal{I}_\infty^k$ which projects on the center $Z(\mathbb{C}[\mathcal{S}_k\wr \mathcal{S}_n])$ for each $n.$ We show that $\mathcal{I}_\infty^k$ is isomorphic to the algebra of shifted symmetric functions on many alphabets.