Though I cannot give you a truly good answer, I may be able to add a bit of direction.
First, as you may know, Parmenides survives only through a very few ancient fragments, ancient references, and Plato's narrative. Yet strangely, much of modern physics remains "Parmenidean" in its treatment of spacetime and the mathematical "framing" of motion or change.
Parmenides asks where "change" or "the new" comes from. Presumably nothing can come out of "nothing," ex nihilo. How can something be contained in or deduced from....nothing? Similarly, if there exists some "thing," how can some "other thing" come out of it? You are, I believe, correct to assume that Parmenides means by "being" roughly existence or "is-ness." Some thing "is." Such concepts are so basic, so omnipresent, that the difficulty lies in pulling them into our awareness. Where something "new" comes from seems completely unproblematic to most of us.
But if you accept basic rules of noncontradiction or the excluded middle, etc., then we start off at the most fundamental level with an enormous paradox. Things "exist" or "don't exist." But how do they pass from one to the other? It is well worth reading the opening of Hegel's "Science of Logic" to ponder this problem. And "ponder" is the right word. You don't just "work it out" logically.
The problem then is explaining or defining flux, transformation, or "motion" of any sort. This is hardly as arcane or as settled a matter as some think. It is the whole career of modern science since Galileo. It impinges on calculus and physics and measurement problems at many, many levels. And it is difficult because it is way, way too basic.
The reference to Aristotle's "potentia" brings in one of many intermediating concepts designed to handle this "is/is not" transition problem. We introduce "becoming" or "possibility" or "could" or "dialectic" or "Trinity" or some other acceptable covering term for the officially "excluded middle." We accept that identity is simply unstable.
When you say you have difficulty grasping this, welcome to the club. If you are asking within the context of philosophy studies, I would argue, at the risk of "moralizing," that philosophy is not all logic and computing, "either/or" but also requires sinking into possibly unanswerable questions in language and the living history of human consciousness. Parmenides remains in our texts because he raised a question so fundamental it still perplexes modern physics, while also generating endless answers.