Next to the kitchen => this is the storage room. If you go a bit south and take the first SW room there, you'll meet Rashax, an imp. If you have the quest from cook Bryant: "Kill rats in storage room" - he will give you the key.
Room with stairs => I think you mean the exit room door to Act 2. The key is in the east chamber of Samuel's lair. His DK there drop 2 keys - both open the chambers there. Did you miss one rune key?
