When you said "Kahn" to help did you mean Papa? Try talking to Papa Kahn again. Ask if he is willing to help the NCR (ask him this while in the main hall with Regis there). After you ask him that (I think you already did and that's why it said talk to Regis) you have to ask Regis how he feels about the NCR. You probably asked him earlier but I had to ask him again to trigger the next possibility.
Spoiler Papa Kahn will not help the NCR fight the legion- you may have misunderstood the conversation. He can sign a treaty and agree to leave the region- but he has too many bad memories about what happened at bitter springs. His son may mention, if you ask him how he feels about the NCR after you ask Papa if he will help the NCR one last time, that if Papa weren't around he would probably not have a problem helping the NCR. You have to report this to Colonel moore if you want to go with it. Otherwise convincing them to leave should be sufficient to satisfy Moore- though I think she's always happier when you come back soaked to the hip in the blood of some faction.)
Huh? Listen, on my playthrough. I haven't killed anybody. I killed Papa Khan as a test, but not on my main save.
In my game, I'm doing it 100% diplomatically, and I'm at the point where I've talked to Khan who says he'll help fight the Legion. "Oh My Papa" then asks me to talk to Regis. If I go to Regis, I can ask him how he feels about the NCR, and he tells me he might be willing to join me. He's told me the exact same line once before, but this time, it crosses of a quest objective.
THE TROUBLE IS, as I already said, that the quest now "hangs." I get no new objectives.
So, to be perfectly clear: I've done things diplomatically, I've talked to the people in charge, I've done all the objectives, but the quest doesn't progress.
Please help me out here, as I this is an almost game-stopping bug.