Don't worry, even native English speakers find it difficult to understand. And by that I mean that we can read it and tell you what each word means, but it's so steeped in symbolic imagery and allegory that if you asked the average person to read a stanza aloud and then ask them what happened, they would struggle to do so.

What really helps are having glosses or footnotes, where the references can be explained. Unfortunately most commentaries are not public domain, so you may have to shell out some money for a good one. But they were invaluable when reading Shakespeare and Dante, as it made the difference for me between reading Dante and understanding Dante.

I am also a non-native speaker...

my method to read those old English text is to first read a summary or outline (in modern English) of the original work, and then perhaps find some more modern English material on the subject to deepen my understanding...but eventually, I would try to read the original work, as the melody (they call meters; but I feel it is essentially isomorphic to rhythm in music) and the rhyme in those works written by Shakespeare, John Donne, or John Milton (as well as many other great writers) are really really superb, and not that different than the corresponding parts in literary works in other languages.

Reading a summary and outline would help you to gain some contextual information, and then you could use some redundancy in human language to get better the intended message the writer hopes to convey...

I suspect many native speakers would have difficulty too, because of the age and style of the poem. For me, the difficulty is part of the enjoyment of studying older texts, teasing out the meaning gives me a mental thrill similar to coding.

Most native speakers finds the language pretty hard to fully understand.

There is however a pretty good modernized version of Paradise Lost by Joseph Lanzara that will give you a good understanding of the story.