She stands around at the hidden camp before Quest 8, right at the edge of the cliff. Like Captain Rumford in New Tristram she always only has one topic at a time, and one of these topics will make her drop her poem.
For Kala, go back to quest 7, then go talk to her in the Hidden Camp. I just found the Love Letter in a Keepsake Box in Dahlgur Oasis, just NE of the northern most waypoint.
I was able to find Kala's Poem after I spoke to Kulle in Act 2, Quest #7 Blood and Sand with the conversation with Kala "Noble Dreams".