Yes. There are two approaches. In the spirit of your pairing, not that on three elements you can go $(1\ 2\ 3)\to (2\ 1\ 3) \to (3\ 1 \ 2)$ and permute back to $(1\ 2\ 3)$. Now for a large odd number, do this once and as many pairs as needed.
Another way is to pick $n-2$ permutations at random. Pick the $n-1$st not to be the inverse of the product, so the product of the first $n-1$ is not the identity. It will be a permutation and have an inverse in the permutation group, so take that inverse for the last permutation.
Now that you require the permutations be multiplied in any order, your solution for even works as long as you can reuse permutations. Take $k/2$ copies of a permutation and $k/2$ copies of its inverse. As elements of a group commute with their inverses, you can multiply these in any order to get the identity. If you have at least five elements you can do odd. Take three copies of the rotation of three elements and $k-3$ copies of the swap of elements four and five. As these are disjoint, they commute. If you want to avoid reusing permutations, even still works if you have enough elements. Take a pair of a permutation of three elements and its inverse $k/2$ times with the pairs affecting pairwise disjoint sets of elements. I don't know if you can do odd in any order without reuse.