I think you already have your answer: if you've been told to aim higher by several people who know your work better than we can, then aim higher :-)

More philosophically, it's a good idea to take an empirical approach to your own career. Don't make too many assumptions about what will or won't get published; instead, try out different strategies. In this case, you know that you can publish your results on lower-ranking journals. Now it's time to do the experiment where you try for higher-ranking ones.

As for which specific journals, why not ask the people who posed the problems to begin with? Or think about where you'd like to read this kind of result. On a more specific level, you might think about your introductory paragraphs, and what is the broadest possible audience to whom you'd be able to explain why your results (the results! not the proofs!) are interesting.