The rock is a seal of sorts... you see that kind of thing in anime sometimes...
The rock itself is heavy and all that, but as long as the seal is there; you won't be able to move it. (That or it is used to keep what is in it, in; and maybe something in particular out)
It is hinted that Jenka created the Labyrinth to protect the Core aka the heart of the island. So it stands to reason that the rock was placed there by Jenka (or Misery).
I don't think Curly and Quote helped move the rock at all. Balrog CLEARLY able to move it by himself, since they couldn't budge it; yet he throws it way up in the air like it was nothing.
But, what about the seal you say?
Well Balrog and Misery are somehow related to the Ballos / Jenka island family. I get the impression Balrog has been with Misery for a Long time; probably since the creation of the Demon Crown, from Balrog's comments. Also, Balrog had no problem taking the key from Jenka earlier.
It's possible that Balrog being connected to Misery's fate, or just because he's that awesome of a magical something creature that he can break magic barriers and stuff.
I'll go out on a limb, but what if the seal on Ballos was supposed to keep out everyone and everything/as well as keeping them in. But, Balrog has no issues going anywhere he wants [HUZZAH]. Perhaps that is why Misery could not just teleport in... Balrog is an exception.
That huge death trap that broke the barrier to Ballos is... well HUGE. So perhaps, it's somehow similar to Balrog...
meh, I dunno; but in any case Balrog is unique xD
EDIT: I doubt Gaudi made the rock; some of them don't even know what it is they were supposed to guard.