Here is another solution, based on the paper "Robinson-schensted algorithms for skew tableaux" by Sagan and Stanley (Darij Grinberg was the one who suggested that this algorithm might work, I'm just filling in the details in a pretty straightforward fashion).
Fix integers $k$ and $n$, and denote $[n]=\{1,2,\dots,n\}$. We say that
$$\pi=\begin{pmatrix}i_1 & \dots & i_m\\ j_1 & \dots & j_m\end{pmatrix}$$ is a partial two-line array
if the integers $i_1,\dots,i_m$ are distinct elements of $[n]$, the same is true for $j_1,\dots,j_m$, and $i_1<\dots<i_m$.
Also, fix some partition $\mu$ with at most $k$ rows, and assume all parts of $\mu$ are much bigger than $n$ (the correct way is to think of $\mu$ as a lattice path inside an infinite horizontal strip of height $k$).
We say that an SYT $P$ with at most $k$ rows has right boundary $\mu$ if it has shape $\mu/\nu$ for some $\nu$. A similar definition goes for SYT with left boundary $\mu$, and the original conjecture becomes $$\#\mathrm{SYT}_k^n(\mu/*)=\#\mathrm{SYT}_k^n(*/\mu)$$
where the LHS denotes the number of SYTs with $n$ boxes with at most $k$ rows and right boundary $\mu$ while the RHS denotes the number of SYTs with $n$ boxes with at most $k$ rows and left boundary $\mu$.
One more definition: a partial SYT with entry set $S$ is just a Young tableau (i.e. the entries increase along rows and columns) with distinct entries such that the set of its entries is $S$. For example, an SYT with $n$ boxes is a partial SYT with entry set $[n]$.
We are going to describe a bijection $(\pi,T,U)\leftrightarrow (\tau,P,Q)$ where
$\pi=\begin{pmatrix}i_1 & \dots & i_s\\ j_1 & \dots & j_s\end{pmatrix},\quad \tau=\begin{pmatrix}i'_1 & \dots & i'_t\\ j'_1 & \dots & j'_t\end{pmatrix}$ are partial two-line arrays;
$T,U$ are partial SYT's of the same shape $\mu/\lambda$ with entry sets $[n]\setminus \{j_1,\dots,j_s\}$ and $[n]\setminus \{i_1,\dots,i_s\}$;
$P,Q$ are partial SYT's of the same shape $\nu/\mu$ with entry sets $[n]\setminus \{j'_1,\dots,j'_t\}$ and $[n]\setminus \{i'_1,\dots,i'_t\}$.
This bijection is going to work in exactly the same way as in Sagan-Stanley's paper, so we're going to redefine their internal and external insertions.
Let $R$ be a partial SYT with entry set $S$, and let $q$ be an integer not belonging to $S$. Then define the external insertion of $q$ into $R$ to be the new partial SYT denoted $R\leftarrow q$ and defined by the following algorithm: we first row-insert $q$ into the first row of $R$, then it bumps out some element $q_1$ which we then insert into the second row of $R$, and so on until either $q_i$ is just appended on the right to the row $i+1$ of $R$ (i.e. nothing is bumped) or we reach $k$-th row of $R$ in which case we get one extra entry $q_k$ of $R$ which we memorize.
Similarly, let $(i,j)$ be an inner (that is, left) corner of $R$. Define the internal insertion of $(i,j)$ into $R$ to be the new partial SYT denoted $(i,j)\to R$: remove the entry $q$ from $(i,j)$ and insert it into the next row $i+1$ of $R$. It bumps out some entry $q_{i+1}$ which we then insert into row $i+2$ of $R$ and so on until either nothing is bumped or we reach row $k$ in which case we memorize the extra entry $q_k$ that we get.
Now, here is the RSK algorithm that is going to solve the problem:
- initially, set $P=T$, $Q=\mu/\mu$ an empty tableau and $\tau:=\begin{pmatrix} \\ \end{pmatrix}$ an empty partial two-line array;
- for each $q=1,2,\dots,n$, do the following:
- if $q$ belongs to the entry set of $U$, then $q$ lies in an inner corner $(i,j)$ of $U$, so remove it from $Q$ and replace $P$ by $(i,j)\to P$;
- otherwise, if $q$ is equal to $i_m$ for some $m$, replace $P$ by $P\leftarrow j_m$;
- if we memorize an extra entry $p$ of $P$ as a result of our insertion, append $\begin{pmatrix}q\\ p \end{pmatrix}$ to $\tau$;
- otherwise, append $q$ to $Q$ in the box that was added to $P$ at the final step of the insertion.
It is easy to see that this is indeed a bijection. Another property that can be proved analogously to Theorem 3.3 in Sagan-Stanley's paper is the following symmetry of the algorithm:
if $(\pi,T,U)\leftrightarrow (\tau,P,Q)$ then $(\pi^{-1},U,T)\leftrightarrow (\tau^{-1},Q,P)$.
Here $\pi^{-1}$ is obtained from $\pi$ by first switching $i_m$ with $j_m$ for all $m$ and then sorting the columns so that the first row would be increasing. As a corollary of that, we see that the triples $(\pi,T,T)$ where $\pi=\pi^{-1}$ is an involution correspond to the triples $(\tau,P,P)$ where $\tau$ is an involution (Sagan-Stanley, Corollary 3.4). Therefore the following formula is true:
$$\sum_{s=0}^n \mathrm{Inv}(n,s) \#\mathrm{SYT}_k^{n-s}(\mu/*)=\sum_{t=0}^n \mathrm{Inv}(n,t) \#\mathrm{SYT}_k^{n-t}(*/\mu),$$
where $\mathrm{Inv}(n,s)$ is the number of involutions $\pi$ with $s$ columns and with entries from $[n]$. This recurrence immediately implies the result by induction on $n$.
One can consider the semistandard version (the Knuth version) of this RSK algorithm which shows the following identity:
$$\sum_{\lambda\subset \mu} s_{\mu/\lambda}=\sum_{\mu\subset \nu} s_{\nu/\mu},$$
where the sums are infinite and taken over all partitions $\lambda,\nu$ with at most $k$ parts (that are respectively to the left and right of $\mu$ in this infinite horizontal strip of height $k$). Of course, this is a stronger statement since the number of SYT's is recovered by taking the coefficient of $x_1\dots x_n$ on both parts. The stronger identity was conjectured by Alex Postnikov.
