Can any software recommendation question be made on-topic by simply asking "how"?
E.g., if the question asks "I am looking for a program that can do X", does rephrasing it as "how can I do X" makes it on-topic?
If the question is about solving a specific problem, it can usually be rewritten to focus on the problem. But not every software rec question can be turned around that way. Just off the top of my head:
To the specific example in the question, "I am looking for a program that can do X": even on the Software Rec site, a lot of additional information is required to make it a good question--platform, criteria, constraints, etc. It needs enough qualifying information so that it doesn't attract an endless list, and there is a way to judge what is a good solution. Expressing something here in the form of a problem should have similar specificity.
"How can I do X" needs more meat to ensure that "Use program XYZ" is not an answer. It needs to be worded to attract an actionable solution, which can include a recommended product as part of that.
In terms of being too broad, that can be somewhat contextual. If it attracted 10 detailed solutions, each substantially different, and each using a different recommended product, that probably wouldn't be a bad thing. But generic problems that can be solved using dozens of tools are more likely to be considered too broad than ones where one or two tools dominate. It may mean that the person hasn't done a simple Google search yet, or the question needs more specificity.
Journeyman Geek's answer talks about software requirements vs. problem requirements. There could be overlap. But the key point there is that one addresses "meta issues" about the software, like how you want the UI to work, or the ability to customize things. The other addresses the problem you need to solve and the constraint imposed by the problem.
A good software recommendation question on SU isn't about the product; it's about the process. Implicitly you're expected to give a fair bit more information, and in some cases, the answer might not require additional software at all.
Contrast this with software recommendations where you're looking at a list of requirements for software - we'd rather focus on the process and workflow. It's not as simple as just rephrasing, but it's a start.
You often can rephrase a question seeking a software recommendation into one that asks about how to accomplish a goal, but as fixer1234 discussed, there are many cases where it isn't quite that simple.
By asking "how do I solve Problem X?" (for some sufficiently well-defined value of X), any good answer that suggests a tool will automatically have to discuss how to use that tool to accomplish the stated objective. The answer might still suggest a tool, but it will have to go beyond this. Different people can also suggest different tools, but each needs to discuss how to use that tool; it's even possible that what you are trying to do can be accomplished with widely installed tools shipped with the OS, so no extra tools are necessary.
An answer to such a question that simply states "Use Tool Y" will almost certainly be a case of Your answer is in another castle: when is an answer not an answer?, but an answer that says "Use Tool Y; if you use it like this, then it will solve your problem" (for some sufficiently well-defined value of "like this") will be an answer. Not only can the meat of the answer (the process) be applied to other programs as well to accomplish similar goals, but it also requires that whoever writes an answer actually tailors that answer to the specific problem.
Even the Software Recommendations SE has extensive guidelines on what is required for a question to contain "enough information" to be able to produce a reasonable set of answers.