Guess the number, with lying allowed

Run the usual binary search algorithm. Either you get the answer, or you get an inconsistency (an empty candidate set). If you get an inconsistency, Alice must have lied at least once. Restart the binary search. Unless I'm missing something, after O(k*log(n)) steps you will get the answer (plus a lower bound on how many times she lied). You don't need to know k a priori.

I think it's still O(log n), because you specified that Alice can only lie a constant number of times. This means she can at most multiply the amount of guesses Bob makes by a constant.

Imagine that Alice can lie 5 times. Now, no matter when alice lies, she'll end up having to contradict herself. Bob will notice this, and can start his binary search over. Alice is also restricted to lying within O(log n) guesses, or else Bob will guess the number correctly and Alice loses her chance.

So, in the worst case, where Alice lies five times, each /just before/ Bob gets the answer, she has simply caused Bob's binary search to take 6*(log n) guesses (five lies + one correct answer), which is still O(log n).