A (wonderful) discussion of this problem can be found in Nielsen and Chuang (Sec. 6.1.4 Performance). The number of marked elements is labelled $M$ below (instead of $k$ in your case) and the emphasis is mine.
tl;dr if you know $M \geq N/2$ then just randomly pick an item: this has a success probability at least one-half and only requires one call to the oracle. If it is not known whether $M \geq N/2$, then, double the search space (which can be done by adding a single qubit since $N = 2^n$, where $n$ is the number of qubits) with the new $N$ elements such that none of them are solutions to the search -- as a consequence, the number of marked elements is now less than $N/2$.
Here's the quoted section:
If $M$ is known in advance: What happens when more than half the items are solutions to the search problem, that is, $M \geq N/2$?
[...] the number of iterations needed by the search algorithm
increases with $M$, for $M \geq N/2$. Intuitively, this is a silly
property for a search algorithm to have: we expect that it should
become easier to find a solution to the problem as the number of
solutions increases. There are at least two ways around this problem.
If $M$ is known in advance to be larger than $N/2$ then we can just
randomly pick an item from the search space, and then check that it is
a solution using the oracle. This approach has a success probability
at least one-half, and only requires one consultation with the oracle.
It has the disadvantage that we may not know the number of solutions
$M$ in advance.
In the case where it isn’t known whether $M \geq N/2$, another approach can be used. [...] The idea is to double the number of
elements in the search space by adding $N$ extra items to the search
space, none of which are solutions. As a consequence, less than half
the items in the new search space are solutions. This is effected by
adding a single qubit $|q \rangle$ to the search index, doubling the
number of items to be searched to $2N$.
