If each paper cites the other, then yes you can submit both papers simultaneously for publication -- that is, there is no ethical or procedural problem with doing so.
However, like most things that are possible and ethical, you may or may not actually want to do it. I think it is worth some discussion of pros and cons. I will assume that you are seeking an academic career in mathematics: otherwise much of this will not apply to you (but will, I hope, to some readers). Here are some questions to guide the discussion:
Are the two papers of independent interest? That is, would an expert in the field who had both in hand want to read both?
If the answer is yes, then it would be very reasonable to publish both. Two papers solving the same problem is not an issue: as you point out, new proofs of old results are commonplace in mathematics papers. (Most often new proofs are not viewed as work of the very highest level, but sometimes they are, and I'm sure we all have our favorite examples. Anyway, most published mathematics is not "work of the very highest level.") However if you are publishing a second proof of a known result, then you have to explain the novelty of the approach and not just of the result itself. But anyway, there is no question that a different proof of a result is not "the same work" in the sense that the journals are warning you about.
Would it make sense to combine both proofs into a single paper? Would it be profitable to do so?
Sometimes the same work has multiple proofs of a single result. This is a good way of signalling that neither approach is clearly superior and also provides a natural opportunity for comparison -- for instance, perhaps each proof can also be made to yield further results that the other cannot. Or maybe one is shorter but the other is more self-contained/elementary.
By the second question, I mean the (perhaps difficult) one of how the community would view one paper containing two proofs versus two papers published at about the same time. This is a very "sociological" question that I don't see how to answer in a principled way: it really just depends what people believe. My understanding is that most parts of science outside of pure mathematics are much more tolerant of "parallel publication" than pure mathematics. (Gian-Carlo Rota quipped that the value of a mathematician is judged by taking their worst paper and dividing by the number of papers. Like any good horror story, it has just enough basis in reality to scare us.) Within pure mathematics parallelism is better received in some areas than others. But it is definitely possible that if you combine the two works you could publish both of them in a better journal than you could otherwise publish either one (and moreover, in most parts of pure mathematics, if journal A is clearly stronger than journal B, it is probably better to have one paper published in journal A than two papers in journal B).
Even if one paper largely or completely supersedes the other, does the chronology of the work justify publishing both?
Academics are temporal beings and also temporal workers: whereas some artists can work on something for years or decades and show you only the finished product, almost no academic can get away with saying "I am working steadily on a very promising programme. I will show it to you when I've finished it and then worked out the best possible presentation, some years from now." In practice, it is usually the case that you publish things that have not been put in their final form (I mean this in a demanding intellectual sense). I worked hard for about five years with a junior collaborator (first a postdoc then an assistant professor, whereas I was already tenured). When we would get a nice result, it would really excite me and point to the next result...which I would often want to put in the very same paper that we were working on. This made my collaborator justifiably nervous. Our last two joint works were about 50 pages each, published in the same year though we had spent at least three years working on them. Ever since then I have been pursuing implications of this work, and I currently have a preprint that is nearing 100 pages. If we had waited ten years, we could have published one article or book where everything fits together beautifully. But that's not how academic work works, most of the time.
On the other hand, you describe having prepared the second article in the "few days" after submitting the first one. Perhaps you don't realize that the first article is going to spend, most likely, the better part of a year or more at various stages of the refereeing and publication process. It is really not too late to combine the works into one article if you choose. Really!
