Publication in a journal that has now disapeared entirely. Can I publish the paper elsewhere?

I published a paper with some co-authors in a national journal, recently launched, that was promising at the time. It got acceptedafter a few rounds (yay!). Unfortunately, for some reasons, the journal was discontinued a few years later. Now, the paper is not accessible, as the journal does not have a website anymore. There are some trace of the paper online (it got cited) but this is all. No one can read it anymore.

Am I ethically allowed to submit the paper elsewhere for publication? It is a bit of a weird situation: the paper WAS published, but it IS not published or accessible anymore...

You paper is still, in principle, accessible through some libraries, e.g. the Library of Congress (but you should check). Even for fully electronic journals, libraries use the LOCKSS system to archive papers published there: https://www.lockss.org.

Your paper still counts as a publication for the purposes of academic advancements. Regardless who holds the copyright, publishing it again (likely) would not be looked at kindly by the academic institution where you are in, and I recommend against doing this. (You also will get into trouble with another journal where you would attempt to publish your paper since their copyright agreement would typically contain a sentence similar to "...the work has not been published before, in any form, except as a preprint.")

Some publishers allow you to post a prepublication version of a published paper on arXiv, or bioRxiv or on a personal website, even if you do not hold copyright. (But you would have to check with the publisher first.) If they allow this, this would be my suggestion.

There is one more option: If you are planning to write a book on the subject related to your paper, you can include material based on your paper (but don't copy it verbatim).

You can't publish something for which you don't hold copyright. In the past one almost always gave up copyright to the publisher. Today, in some systems, it might be only a perpetual but non-exclusive license that you give them. Back then, authors were given back a license for some uses, but probably not the right to republish. You were given some documents when you turned over copyright or a license. Try to find those so that you know what rights you retain.

If you don't have copyright or a very broad license, then you can try to contact the publisher of the original journal (or any successor) and attempt to get back your copyright. They might be fine with it if they have no further economic interest in the paper. But it is up to them.

Note that the publisher may still exist even if the journal does not. And if the publisher has gone out of business they may have passed all assets to a successor company. Those assets would include any copyrights they hold. You might need to do some research or hire an IP lawyer to work it out.