To my understanding as well, the 된 in 된장 is the adjective form of the verb "to be thick or hard." It could be argued that this is just another usage of 되다 "to become/develop into," but Naver dictionary distinguishes the two.
As for the adverb 되게, this is a really tough one to lay an exact origin on from what I have read. In my mind personally, it makes more sense though to look at 되게 as an adverbial derivative of the "to be hard" version of 되다.
Since the "to become" version of 되다 can be translated into about 40 distinct verbs in English, someone probably could find a way to argue for 되게 being derived from the "to become" version. But my stance is that all of the uses of 되다 you use are of the "to be hard, thick" version of 되다.
So, the short answer on the question is that 되다 has two branches of meaning:
- To become/to be expended/to be fulfilled/to come to pass.....etc. You get the idea.
- To be hard or thick or extreme. Very much so.
The first branch of meaning is pretty much the usage whenever 되다 is used to mean ANYTHING BESIDES "to be hard, thick, extreme." This is how every dictionary I have consulted treats 되다.
Let's just hope that no one asks us to dissect the sentence "된장이 되게 되게 된다." (The 된장 is becoming extremely thick.) Wow.