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
I'd started preparing a response, but the OP seems to have lost interest. In any case for the benefit of future Readers here are my initial thoughts. If there are Comments I'll be glad to fill in more details.
The variant of the Secretary Problem considered here appears in the literature as early as 1966 with publications by:
Although both of these links lead to papers behind paywalls, as far as I can tell, a good summary of the results by Gusein-Zade can be gleaned from this open access technical report by Frank and Samuels (1979) . In particular as the number of secretaries $N \to \infty$, the asymptotic chance of success for the classic problem $1/e \approx 0.3679$ rises to roughly $0.5736$ when choosing either the best or second-best candidate counts as a success.
The general rule that maximizes the chance of getting one of the $b$-best secretaries is shown by Gusein-Zade to have the form of $b+1$ consecutive intervals subdividing the interviews $1,\ldots,N$.
In the present case $b=2$ and there are three phases of the rule. In the first phase the interviews $1 \le i \le N\cdot m_1(N)$ are conducted and the relative rankings observed without stopping, In the second phase the interviews $N\cdot m_1(N) \lt i \le N\cdot m_2(N)$ are conducted and only stop if one interview results in a relative "top" ranking (better than all previous interviews) happens, in which event the interviews are ended with a job offer being made. If the second phase finishes without a job offer, the third and final phase of interviews $N\cdot m_2(N) \lt i \le N$ applies the rule that a job offer is made if and only if an interview results in a relative ranking of "top" or "next to top" (better than all but at most one of the previous interviews).
It is useful to express the boundaries between phases as coefficients $m_1(N),m_2(N)$ because these multipliers have fairly simple limits as $N\to \infty$, namely as Gusein-Zade showed:
$$ \lim_{N\to \infty} m_2(N) = \frac{2}{3} $$
and:
$$ \lim_{N\to \infty} m_1(N) = \varphi $$
where $\varphi$ is the unique solution in $(0,1)$ of:
$$ \varphi - \ln \varphi = 1 - \ln(2/3) $$
Now $\varphi \approx 0.3470$, and the exact limiting probability of success for large $N$ is $\varphi (2-\varphi)$, whose approximate value $0.5736$ was mentioned before.