You would shuffle your discard to make a new deck and KO a card.
This is correct. Any time you need to interact with your deck and it is empty, you reshuffle your discard pile into your deck then interact with it as necessary. If both deck and discard are empty, then there is no effect. Please check out the faq linked on the base game's page for this and many other answers to questions!