Regarding (which it seems was so far not answered)
Generally speaking, are papers who answer a respectable open question judged more for the problem solved than for the difficulty/innovation of the solution?
In general, in my opinion and observation, more for the problem (by those that knew about the problem to beging with). If there are people that knew about the problem, perhaps even thought about it themselves, yet could not answer it, and now it is solved then this is remarkable. The following is a matter of taste, but one can (and I do) even find a 'simple' solution to a known problem more impressive than a 'complicated' one. If there is a 'simple' solution that sofar nobody found, than actually it was not at all 'simple' even if in hindsight it perhaps looks like this. Yet, a long complicated one, perhaps people even suspected it could work like this, but just did not do it out of some form of lazyness or fear of spending a lot of time and then it would not work. Also, a new simple proof of something known might be interesting, a new (more) complicated one rather not (exceot perhaps it comes along with some conceptual insight or surprising connection).
Yet, since you stress the subfield aspect, regarding the choice of the journal, it could be a good idea to submit it to some editor that is likely to have known about the problem. Or, at least to make in the introduction quite clear that what you are solving is a known problem around since a while. Otherwise you run the risk that this aspect is overlooked, and then it could/would be more about difficulty/innovation of the solution.
Regarding specific journals, I think the situation you describe is quite general, so that I would not know what to suggest based on this. Except perhaps: some journals have specific restrictions regarding the lengths of papers. So in case your papers should be short (say less than ten pages) and you should be
worried about this, you could (but don't have to) pick a journal with an upper bound on the lengths.
The Proceedings of the AMS are one example, the Bulletin of the LMS another one (though in the latter case you would just submit to the LMS and they would choose the precise venue).
Another general strategy (not always a feasible option) is to submit the solution to a problem to the/a place where the problem was raised.
Finally, I agree that asking people familiar with the situation and trying things out is good advice. And, a rejection of a paper is not the end of the world. So, if you do not need the acceptance/publication quickly, why not try to aim high, if ever the paper is 'thrown back at you' you still can aim lower later, while the converse is not possible. (Needless to say, one should not overdo this, as it causes work, and delay, for various people, but to try it on oaccasion seems certainly fine.)