Generally, the player decides
From the Recall Knowledge entry in Skills and Action,
The following skills can be used to Recall Knowledge, getting information about the listed topics. In some cases, you can get the GM’s permission to use a different but related skill, usually against a higher DC than normal. [...] The GM might allow checks to Recall Knowledge using other skills. For example, you might assess the skill of an acrobat using Acrobatics.
As written, the player declares that they are trying to Recall Knowledge using (Skill). The GM then decides if that is an acceptable action and rolls the check (it's a Secret check), providing any information (or lack thereof) gained.
However, it's not unreasonable to ask which skill(s) would be appropriate
The list of "appropriate" skills are a generic list that allow you to get going. There are instances where a GM may wish to deviate from the provided table; for example, it would not be unreasonable to allow Recalling Knowledge about a Flesh Golem using Religion to compare it to undead (in addition to Arcana and Crafting). I'm sure there are creatures that normally appropriate skills don't make sense. There is no reason the GM couldn't let the players know which skills they intuit would be effective.
Of course it is up to each group if this is something that is allowed, regular, or if the players expect the GM to be upfront about the skill examples provided. As written, the GM is under no obligation to provide anything more than a description of the creatures encountered.
In my experience, it goes most smoothly when the GM is upfront about what skill(s) are acceptable to roll unless there's a reason the characters wouldn't know to roll that skill (IE illusion magic). Trying to limit player knowledge more than character knowledge rarely pans out well; it does not magically remove meta play nor does it provide fun moments.
Side note: Failing Forward
When the player spends an action, they're usually hoping to get some benefit. For 1/3 of their turn, it's not unreasonable to make a best effort to provide some information, even if it's less useful than they hoped.
Following off your example, you may tell the player rolling Nature "This being seems wholly un-natural... constructed and magically empowered." to inform them of more appropriate skills. If they were instead attempting to roll Religion (and rolled sufficiently high, probably against a greater-than-normal DC), you may be able to provide some details about the creature "You realize it's not actually possessed... it would respond to positive energy if so, but this thing doesn't and seems to be resisting physical damage, like an object".