The right tool to know if string theory is science would be indeed a demarcation criteria. Such a criteria can be used toward creationism as well as string theory to sort out metaphysics from science.
Creationism asserts something about the world that would explain our observations (it explains animal species by the hypothesis that God created animals as they are now some time ago). Similarly, string theory asserts something about the world that would explain our observations (that everything is constituted of strings at a fundamental level, which would explain all physical phenomena). This is a feature of scientific theories more generally: newtonian physics asserts that there are forces and masses to explain the movement of objects. The point of the demarcation problem is finding a criteria to sort out the assertions of this kind that can be called scientific or not.
The problem is that we have no uncontroversial criteria today. We want science to be more empirical than metaphysics, which is why criteria of testability or refutability were often invoked, e.g. by Popper. But all scientific theories have untestable claims at their core (such as the principle of inertia in Newtonian physics, which requires an inertial frame of reference to be meaningful, but then it is circular). They have empirical consequences only when all axioms of the theory are taken together to create models, and this requires practical knowledge or auxilliary hypothesis that are external to the theory to map empirical data with theoretical models. Even then it is always possible to invoke an ad-hoc hypothesis to save the theory from experimental failure (for example, planet Vulcan was invoked to save newtonian physics).
Couldn't we say that astrology and creationism are bad refuted theories rather than pseudo-scientific ones? They are on a par with scientific hypothesis in that they make untestable claims with observable consequences, but they are not well supported by current experimental data (fossil records) or fit badly with other well accepted theories. Lakatos thought that what makes a theory scientific is only that it is a fruitful research program that explains more and more phenomena rather than a degenerating one that makes no novel predictions.
Similarly the fact that string theory is based on non testable claims at its core should not be a problem so long as the whole theory can be used to create models that make empirical predictions.
The problem for string theory is that it does not even provide any testable models so far (it looks more like a framework of possible theories with too much parameters to tell which is the right one for our universe), but as far as I know that's more a technical limitation than a principled one. Perhaps we should wait to see if this research program is fruitful or not.
One advantage of string theory is that it fits very nicely with other physical theories. Some philosophers would argue that non-empirical criteria should count, and actually always counted in science: explanatory power, fruitfulness, unification with other theories, simplicity...
This is up for debate but you're right that this is a debate about the demarcation between science and metaphysics.