Learn Spanish (Latin America): El aliado se quedó perplejo al escuchar el plan. - The ally was left perplexed upon hearing the plan.

Quedarse is the best choice for a state change that happens as a reaction to a specific event or represents a sudden, often temporary, result. Since the ally's perplexity is a direct reaction to hearing the plan, se quedó fits perfectly. Hacerse implies conscious effort or a gradual change (like a profession), while volverse suggests a more permanent or profound change in character.

Could I just use estuvo or estaba instead of se quedó?

You could, but it changes the focus. Se quedó perplejo emphasizes the exact moment of transition (he became or was left perplexed right then). Using estuvo or estaba perplejo merely describes the state he was in, without highlighting the sudden emotional change triggered by the plan.

How does the phrase al escuchar work, and could I just say cuando escuchó?

The structure al plus an infinitive verb is a very common and efficient way to say upon doing an action or when an action happens. You absolutely could say cuando escuchó el plan, but al escuchar is highly natural in Spanish to connect two simultaneous or immediately sequential events.

Does the adjective perplejo need to match the subject?