I think the flaw in your reasoning is here:
For $k=2$, since always the first candidate is hired, we should have
$f(1)=2$ (meaning that the first candidate should be the second-best
one).
For $k=2$, let us say that $f(x_0) = 1$, we only need that for all $i$ with $2 \leq i < x_0$ we have $f(i) < f(1)$. This means that the first person can be the 5th best candidate, as long as only worse candidates come after him/her till we reach the best candidate.
Given this, you then need to, for each possible position of the best candidate ($2 \leq x_0 \leq n$), find what are the values possible at the first position and then find, for each, the total number of possible permutations.
ADDENDUM
Let $r_i$ be the rank of the candidate at position $i$.
As assumed above, let $x$ be the position of the rank $1$ candidate ($r_x = 1, 2\leq x\leq n$). Let $r_1$ rank of the candidate at position $1$.
We now know that the ranks of all the candidates at position $i$ such that $1<i<x$ are higher than $r_1$ to allow for only two selections, since $r_1$ is always selected and the next selection can only be at $r_x$. There needs to be, for any given $r_1$, $x-2$ such numbers at least to fit the space between position $1$ and $x$. This restricts the possible $r_1$ to $2\leq r_1\leq n-x+2$.
Now, we just need to find the possible permutations. Given any $x$ and $r_1=y$, we have precisely these many permutations possible where the first term is the number of ways to select $x - 2$ items from $n - y$ items (i.e. selecting valid $x-2$ ranks which are greater than $y$) and the remaining two terms are the number of ways to arrange the selected $x-2$ items between $1$ and $x$ and the remaining $n-x$ items after $x$:
$$\binom{n - y}{x - 2}(x-2)!(n-x)!$$
Hence, to calculate overall number we sum for all possible $x$ and $y$:
$$\sum\limits_{x=2}^{n}\sum\limits_{y=2}^{n-x+2}\binom{n - y}{x - 2}(x-2)!(n-x)!$$
This needs to be divided by $n!$ to get the probability.
PS: I am not sure if this is the correct equation. You can try comparing the result of this to the alternative solutions, and I will be happy to know the result and modify if necessary.
Best Answer
Let $P(n,k)$ be the probability of exactly $k$ hires among $n$ candidates. I'm not sure that there's a compact algebraic formula for $P(n,k)$, but there's a simple recursive one. We have the boundary conditions, $$ \begin{align} P(n,k)=0,\ k>n\\ P(n,1)=\frac1n\\ P(n,n)=\frac1{n!} \end{align} $$ Call the least favorable candidate $1$, the second-worst $2$, and so on. If candidate $m$ comes on day $1$ the $m-1$ candidates worse than $m$ may be ignored and we will hire $k$ candidates if and only if we hire exactly $k-1$ from the remaining $n-m$. Since the probability that candidate $m$ is the first to show up is $\frac1n$, we have $$P(n,k)=\frac1n\sum_{m=1}^kP(n-m,k-1),\ 1<k\leq n$$
P.S
As you suspected the accepted answer for the cited question is wrong, but a correct one has been posted recently.