Are questions asking for alternate, more efficient solutions on topic?
Sort of. If phrased in precisely this way, then no—the question is both "too broad" and too "give me teh codez", which we stridently avoid. However, there are plenty of ways to phrase such a question that would make it on-topic for Stack Overflow.
The purpose of the Code Review site is really, as the name suggests, to review code. Proposals of alternative implementations are welcome, of course, and I've posted many of them there, but only when done as part of a larger effort to review the existing code.
Stack Overflow doesn't work that way. It deals with specific, narrowly-focused problems. You hardly ever want to post your exact code here, and you certainly don't want to post very much of it. Instead, we advise you to create a minimal, complete, and verifiable example. That would never be acceptable on Code Review. Why the difference? Because we don't care about reviewing your code; we care about solving your problem.
Can the fact that the code is slow or messy be considered a valid "problem"?
Yes, absolutely. Both of these are problems that we can resolve here. However, it is rather tricky to write a good, on-topic question about these things because it requires you to be very specific about what you're looking for. (And as Martin James pointed out, askers are rarely very good at being specific.)
You cannot simply say, "How can I make this code faster?" You need to define what "faster" means to you. You would ideally do that by telling us what the performance characteristics of your current code is, giving us sample data that you used to obtain those numbers, and then describing what your target performance is. We get a fair number of performance-oriented questions here, and I personally find them a fascinating break from the drudgery of "debug my code for me"-style questions. There's a lot that can be learned from the answers, with very broad appeal and applicability to a wide variety of situations.
At the risk of it being heavily downvoted by some of the more dogmatic members of Meta, I think this question is a pretty well-asked optimization question. (Full disclosure: I answered it.) It's very specific, in that it's isolated to only a very small bit of code and a clear purpose, which is explicitly presented in the question. The asker also goes on to explain what his thoughts were (i.e., what he tried). Some might trigger a bit at the last paragraph, where he requests "any guidance and assistance", but that's just a turn of phrase. If you read and understand the question, and the relevant technologies, it is not prohibitively broad.
Here's another example, this one taking the highly unusual tact of asking for counter-optimizations. This question was actually the subject of its own uproar on Meta, but I like it and think it represents some of the best of Stack Overflow. (Well, after it was edited into shape; the original version is an example of how not to do it.) It is admittedly somewhat broad, but not broad in a bad way or for any of the reasons that we discourage broad questions.
(Note that neither of the above two cited questions would be remotely suitable for Code Review.)
"Messy" is even more difficult, as it requires that you establish an objective metric for cleanliness (or whatever the opposite of messiness is). This can be done, though, and if done, it would form the basis of a valid, on-topic question for Stack Overflow. Best is to contextualize this in terms of a specific problem that you're having when it comes to improving the code. "My code looks ugly, please rewrite it" will never be an on-topic question. (A good hint is that it isn't actually a question at all.) But I can imagine, in the not-so-distant past, a C++ question being presented with an ugly for loop, asking for a cleaner solution that retains the same behavior, and being answered with a suggestion to use a range-based for loop.
That said, I would recommend not asking one of these types of questions until you become an experienced question-asker. Asking good questions is hard enough; don't take on any additional challenges until you have demonstrated the ability to handle it.
...does it really belong on Code Review?
Please be careful about recommending Code Review to people. I've handled several flags recently from people who asked that their question be migrated to Code Review after being told by some helpful person in the comments that they should have asked it there. In the majority of cases, I've felt compelled to decline. Code Review is not simply a dumping ground for questions that you think might be too "opinion based" for Stack Overflow. Even more so than us, Code Review has very specific standards for what types of questions are on-topic there, and unless you write your question with Code Review's standards in mind, it's exceedingly unlikely that it will meet those standards. Most importantly, you need to be presenting the complete, actual code, it needs to be code that you maintain, and it needs to be code that is working.
Would this type of question be acceptable on Stack Overflow?