Symbolic planning algorithms and large language models have different strengths and weaknesses for story generation, suggesting hybrid models might leverage advantages from both. Others have proposed using a language model in combination with a partial order planning style algorithm to avoid the need for a handwritten symbolic domain of actions. This paper offers a complementary approach. We use a state space planning algorithm to plan coherent multi-agent stories in symbolic domains, with a language model acting as a guide to estimate which events are worth exploring first. We evaluate an initial implementation of this method on a set of benchmark problems and find that the LLM's guidance is helpful to the planner in most domains.