She was at a loss as to what to say next.

Literal

She [topic-は] next [adverbial-に] what [object-を] saying [if-good-か] was-at-a-loss.

途方に暮れる ('to be at a loss, to be at one's wits' end') is a vivid set expression: 途方 originally meant 'way, route, course of action,' and 暮れる evokes the sun setting — together, 'darkness falling on one's path.' The structure ~たらよいか embeds a deliberative question ('what should I do?') as the object of the main verb — '~たら' (if/when) + よい (good) + か (question) = 'whether it would be good to.' This is the canonical pattern for 'wonder what to do' clauses.