Perhaps there is something relating odd ordered partitions with even ordered partitions?
There is indeed. Let's try to construct an involution $T_n$, mapping odd ordered partitions of $n$-element set to even and vice versa:
if partition has part $\{n\}$, move $n$ into previous part; otherwise move $n$ into new separate part.
Example: $(\{1,2\},\{\mathbf{5}\},\{3,4\})\leftrightarrow(\{1,2,\mathbf{5}\},\{3,4\})$.
This involution is not defined on partitions of the form $(\{n\},\ldots)$, but for these partitions one can use previous involution $T_{n-1}$ and so on.
Example: $(\{5\},\{4\},\{1,2\},\{\mathbf{3}\})\leftrightarrow(\{5\},\{4\},\{1,2,\mathbf{3}\})$.
In the end only partition without pair will be $(\{n\},\{n-1\},\ldots,\{1\})$. So our (recursively defined) involution gives a bijective proof of $\sum_{\text{k is even}}k!{n \brace k}=\sum_{\text{k is odd}}k!{n \brace k}\pm1$ (cf. 1, 2).
Upd. As for the second identity, the involution $T_n$ is already defined on all cyclically ordered partitions, so $\sum_{\text{k is even}}(k-1)!{n \brace k}=\sum_{\text{k is odd}}(k-1)!{n \brace k}$.
P.S. I can't resist adding that $k!{n \brace k}$ is the number of $(n-k)$-dimensional faces of an $n$-dimensional convex polytope, permutohedron (the convex hull of all vectors formed by permuting the coordinates of the vector $(0,1,2,\ldots,n)$). So $\sum(-1)^{n-k}k!{n \brace k}=1$ since it's the Euler characteristic of a convex polytope.
Start by typesetting the claim using standard conventions. We seek to show that
$${n+1 \brace k+1} = \sum_{m=k}^n {n\choose m} {m\brace k}.$$
The combinatorial proof is extremely straightforward. The left side is the number of partitions of a set of $n+1$ distinguishable items into $k+1$ indistinguishable subsets. (Permutation group $S_{k+1}$ and no positioning on the subsets -- a set of sets.)
The right side counts the same statistic.
Suppose we have a partition into $k+1$ subsets and the item with the label $n+1$ has gone into a subset of size $n-m+1$. (There are $n-m$ other elements in this subset.) Then we must have chosen $m$ elements from the other $n$ items for the other $k$ subsets and partitioned those $m$ items into $k$ subsets, giving a contribution of
$${n\choose m} {m\brace k}.$$
The sum counts all possible total subset sizes for the subsets not containing $n+1$, starting at $k$ because none of the subsets may be empty.
The algebraic proof uses exponential generating functions. Recall that partitions into subsets have the following combinatorial specification:
$$\mathfrak{P}(\mathfrak{P}_{\ge 1}(\mathcal{Z})).$$
This immediately implies that the generating function of the Stirling numbers of the second kind is
$$ G(z, u) = \exp(u(\exp(z)-1)).$$
Now we have
$${n+1 \brace k+1} = (n+1)! [z^{n+1}] [u^{k+1}] \exp(u(\exp(z)-1))
\\= (n+1)! [z^{n+1}] \frac{(\exp(z)-1)^{k+1}}{(k+1)!}.$$
This last term is
$$(n+1)! \frac{1}{n+1} [z^n]
\left(\frac{(\exp(z)-1)^{k+1}}{(k+1)!}\right)'\\ =
n! [z^n] \frac{(k+1)(\exp(z)-1)^k}{(k+1)!} \exp(z) =
n! [z^n] \exp(z) \frac{(\exp(z)-1)^k}{k!}.$$
Expanding the product of the two exponentials this yields
$$n! \sum_{m=0}^n \frac{1}{(n-m)!} [z^m] \frac{(\exp(z)-1)^k}{k!}
= \sum_{m=0}^n \frac{n!}{m! (n-m)!} m! [z^m] \frac{(\exp(z)-1)^k}{k!}
\\= \sum_{m=0}^n \frac{n!}{m! (n-m)!} {m \brace k}
= \sum_{m=k}^n {n\choose m} {m \brace k}.$$
Observe that the combinatorial and the algebraic proof are very similar.
Best Answer
Count non-surjective functions $[n]\to [k]$. Use inclusion-exclusion by counting functions $A_i$ that miss one particular element $i\in [k]$ and then consider $A_1\cup A_2 \cup \dots \cup A_k$.