Minimal number of attempts at a multiple choice exam needed in order to pass, without any prior knowledge
Here is an algorithm to identify the answers with successive attempts.

It has a worst case complexity of $O(m(1+\log_2 k))$

This corresponds roughly to collecting in each attempt one bit of
information on the right answer, for each question in succession.

Of course we cannot do that, because we can only give one whole answer
per question. So the trick in to transpose the problem, by identifying k
correct answers and trying to find their questions.

Apologies for the rough presentation. I am running out of time.

The algorithm

We assume, to simplify the presentation, that $N\geq k$. But it does
not really matter. We also assume that $k=2^p$ for some positive
integer $p$, again to simplify the presentation.

We assume that the only result of an attempt $T\in [1,k]^N$ is a score $s(T)$
corresponding to the number of correct answers. The individual
answers for each question are noted $T[j]\in [1,k]$ for the answer to question
$j$, ($j\in [1,N]$), in attempt $T$.

We define $T_i=i^k1^{N-k}, \forall i\in[1,k]$

The $N-k$ last answers always contribute the same amount $r$ to the result
$s(T_i)$ since they do not change.

Together, the first $k$ answers of all $k$ attempts will produce $k$
good answers, distributed in some way over all $k$ attempts, since for
each question there is exactly one good answer among the $k$ being
proposed.

If one attempt has 2 good answers, or more, for one of the first $k$
questions, then another must have 0. Thus, if the scores $s(T_i)$ are
not all equal, the smallest is equal to $r$. Furthermore, if they are
all equal, then they are all equal to $r+1$. So the value of $r$ is easily determined.

We first assume $\exists r\in[0,N-k],\; \forall i\in[1,k],\; s(T_i)=r+1$

This implies that each attempt has exactly 1 good answer among the
first $k$ answers (to the first $k$ questions). But we do not know which.

We define a second set of $k-1$ attempts
$T_i'=i^{k/2}1^{N-k/2}, \forall i\in[1,k]$

Note, that $T_1'=T_1$, so that k-1 new attempts only are needed,
but the duplication makes things simpler to explain.

If the good answer $1$ in the first $k$ questions in $T_1$ was for one of
the first $k/2$ questions, then $1$ is a bad answer for questions
$Q_j,\; \forall j\in[k/2+1,k]$. Hence all the $T_i$ attempts that had
a good answer for one of these $k/2$ questions will lose 1 point in
score, thus falling to $r$. All other attempts, that had a good answer
in the first $k/2$ questions will have an unchanged score $r+1$.

If the good answer $1$ in the first $k$ questions in $T_1$ was for one of
the last $k/2$ questions, i.e. for questions  $Q_j,\; \forall
j\in[k/2+1,k]$, then all attempts $T_i'$ benefit from that good
answer $1$. Those that had a good answer for the first $k/2$ questions
will keep it and see their score increase from $r+1$ to $r+2$, while
the others will lose their good answer as before, but have it replaced
by the good answer $1$ for one question, thus keeping the score $r+1$.

Thus we can conclude that, if some score decrease, then the firat
attempt $T1$ has a good answer $1$ in one of the first $k/2$ questions,
and if some increase it is in one of the next $k/2$ questions.
Forall other attempts $T_i'$, those with the higher score have a good
answer for one of the first  $k/2$ questions, and those with the lower
score have a good answer in one of the next $k/2$ questions.

Recall that $k=2^p$, i.e. $p=\log_2 k$.

If we number the first $k$ questions in binary, starting from 0, we
can see that this is a way to determine the $p^{th}$ bit of the index
question that is correctly answered by some attempt $T_i$.

If for some $i&gt;1$, the score decrease from $T_i$ to $T_i'$, then
$T_1$ has a good answer for a question $Q$ such that the $p_{th}$ bit
of its binary index is $0$, while it is $1$ for an increase. For the
other attempts $T_i$, those with the higher score for $T_i'$ have a
good answer for a questions with the index $p^{th}$ bit $0$, and the
lower scores have a good answer for a questions with the index
$p^{th}$ bit $1$

It is then quite simple to repeat the procedure identically for each of
the other bits of the binary index of the first $k$ questions.

That makes $p=\log_2k$ series of $k-1$ attempts, in addition to the
first $k$ attempts, that is a total of $k+(k-1)\log_2k$ attempts,
to get the first k answers.

However we can improve a bit on that count. We do $\log_2 k$ attempts
to identify the question associated with each answer, i.e. each index
$i\in [1,k]$. Actually we need to identify only $k-1$ such question.
The last one in necessarily the one that was not found yet.

Thus in the above algorithm, we do not need to compute $T_{k}'$, nor
any of the other attempts of index $k$, except for the first $T_k$ in
the first attempts of the algorithm. Since it is also unnecessary for
$T_1'$ and similar, we only need, at most $\log_2k$ series of $k-2$
attempts, in addition to the initial $k$ attempts, that is a total of
$k+(k-2)\log_2k$ attempts, to get the first k answers.

But this relied on the assumption that each of the first $k$ attempts
has exactly one good answer for the first $k$ questions. What if that
is not the case?

One of the first $k$ attempts had more than one good answer in the first $k$.

Then there is at least one attempt, say $T_h$ that failed on the first
$K$ questions, which means that answer $h$ is wrong for the first $k$
questions.

Actually there may be several such attempts caracterized by the fact
that they have the same smallest score $r$. They can all be discounted
as containing no information for the first $k$ questions, other than the
fact that their index is not the answer to these questions.

Futhermore, for any attempt $T_i$, we know that it has $s(T_i)-r$
correct answer $i$ in the first $k$ questions.

If there is only one answer, it can be identified with the previous
binary technique using $\log_2k$ attempts, given that we can replace
half the answers (as specfied by a bit in their binary index) by $h$
which is known to be wrong (which makes thing simpler than
previously).

If there are two correct answers, the same technique is used with a
small variation. The binary approach is used again for both answers
together, until one of the attempts separates them by indicating a bit
$0$ for one answer and a bit $1$ in the same position of the question
binary index for the other answer. From then on, one answer can be hidden
by using the answer $h$ in the questions corresponding to that index,
while the binary search is resumed for the other answer. Once that
answer has identified its question, it is replaced by the answer $h$
that is wrong so that the search can be resumed for the question of
the second answer.

The same technique can be used independently of the number of answers,
progressively splitting them until only one is searching for its
question, then replaced by wrong answer $h$ when its question is found, so that another can be searched, and
so on.

Since the splitting and searching is based on the bits of the binary
indexes of questions, it is quite clear that this costs never more
than $\log_2 k$ for each question to be associated with one of the $k$
answers.

So the cost in number of attempts for identifying the questions for
the first $k$ answers (I am deliberately inverting the view) is not
more than $k\log_2 k$, to be added to the first $k$ attempts. It might
be a bit less with a finer analysis.

However we can again use the fact that each question has necessarily
an answer, so as to skip the binary search on one line of answers (i.e., one
answer number).

First recall that we simply ignore all answer numbers that correspond
to no answer. Then we also set aside the answer number that
corresponds to the largest number of questions for which it is the
right answer. This corresponds by hypothesis to at least two good answers.

Then we determine the corresponding question for all other identified
good answers, at most $k-2$ of them, with a cost that is at most
$\log_2 k$ for each. The correct answer set aside can then be assigned
to all questions that have not been identified as associated with
another answer.

This makes for a total cost of at most $(k-2)\log_2k$ attempts, to be added to
the initial $k$ attempts, thus again a total of $k+(k-2)\log_2k$
attempts, to get the first k answers, as in the first case.

Overall

The cost of this algorithm, mesured in number of attemps, is bounded by $k(1+\log_2 k)-2\log_2 k$ for
identifying the $k$ answers to $k$ questions (as the above could have been done for any set of $k$ questions.

So for $m$ questions, assuming for simplicity that $m$ is a multiple of $k$, the total cost is bounded by $m/k$ times that cost,
i.e. $m(1+\log_2 k)-(2m/k)\log_2 k$.

Apparently the total number $N$ of questions does not matter. But the last questions are
not considered with this technique, except to identify their global effect to factor it out. We do not take advantage of the fact that some groups of question-answer pairs might be easier to identify (because their costs can be factored, for example). Possibly this could
help for the worst case analysis with a different technique that would identify  patterns of answers that are easier to analyze, but there might be a cost in finding them.

Regarding purely asymptotical complexity: this algorithm is $O(m\log_2k)$