Diffie-Hellman based password challenge response scheme
First off, what you are trying to construct here is called an augmented or asymmetric password-based key exchange (aPAKE). As for your concrete construction:


  Does this scheme work?


Yes, it will be functionally correct.

Does it actually achieve the security guarantees of an aPAKE scheme? No, an attacker can look at the transcript, see $Q_s=[k]Q_a$ and knows both $Q_s$ and $Q_a$ and thus can just off-line brute-force the password.

The first (symmetric) scheme you mentioned suffers from the same problem.


  Could we make a public-key-based scheme for challenge response
  authentication?


This is what aPAKE schemes do, the most notable protocols are:


the Secure Remote Password Protocol (SRP), mostly because it was first to be standardized in RFC 2945.
OPAQUE which is the current state-of-the-art when it comes to (simple) aPAKEs.
If you also want to assume an auxilliary 2nd device for the user, OpTFA is the state-of-the-art.
If the user "only" has a device capable of running an (EC)DH key agreement (like a smartcard), then PTR-PAKE is the best you can get.


Example implementations (in C) of OPAQUE and PTR-PAKE can be found in libsphinx.