If Godel showed that a sufficiently powerful formal system can be consistent or complete but not both, is this equivalent to saying that the law of non-contradiction or the law of excluded middle cannot both hold within a system of logic.
I understand that provability and truth are different things, as was the key message of Godel, so I mean that the LNC or LEM cannot both hold as axioms of the system in regards to provability (i.e. a theorem and it's negation cannot both be proven / either a theorem or its negation must be proven). Hope this makes sense!
BONUS QUESTION: What is meant by "paracompelte logic". I've seen this term a few times but not seen a good explanation. Is paracompleteness to consistency what paraconsistency is to completeness?
Let's ignore Godel for now.
What you've written is rather unclear, but there are indeed analogies between LEM and completeness and between LNC and consistency, although they're somewhat loose (so I certainly wouldn't use the word "equivalent" here).
Specifically, in classical logic we have a semantics according to which each structure $\mathbb{A}$ has an associated theory $Th(\mathbb{A})=\{\varphi:\mathbb{A}\models\varphi\}$. Not every theory of course is of the form $Th(\mathbb{A})$, but the $Th(\mathbb{A})$s have a couple nice properties: namely, $Th(\mathbb{A})$ is always complete and consistent. You can think of LEM as the statement "Every structure's theory is complete" and LNC as the statement "Every structure's theory is consistent."
Of course it is not true that every theory is complete, or that every theory is consistent. Completeness and consistency are nontrivial properties of theories in general. LEM and LNC are statements about the particular theories arising from the semantics we've set up. And crucially, a converse holds too: the complete consistent theories are exactly (up to deductive equivalence) the theories of the form $Th(\mathbb{A})$ for some structure $\mathbb{A}$. The remaining direction is Godel's completeness theorem - and no, that's not a typo, Godel proved both a completeness theorem and an incompleteness theorem!
I've chosen to bring semantics into the picture here. That's not necessary - we can phrase everything in terms of purely formal systems - but I think it does make things clearer initially.
Getting back to Godel, the incompleteness theorem says that if a theory $T$ is "appropriate" then $T$ is not both complete and consistent. We can rephrase this in light of the above as:
Put another way, LEM and LNC really are statements about a particular type of theory, and Godel's incompleteness theorem shows that the "appropriate" theories are not of that type.
Here, "appropriateness" is really a pair of conditions: a strength condition and a simplicity condition. The latter is easy to state ($T$ has to be computably axiomatizable), while the former is a bit technical ($T$ has to represent all computable functions).