Il est déjà descendu en bas de la colline?
Is it correct to also say:
Il est déjà descendu de la colline?
It depends on the context.
Je descends en bas means that I'm going down a level.
Je descends quelqu'un means that I'm killing somebody.
It is also possible to say :
As for your second question : Yes, it is correct. Descendre de la colline established that the hill is in an upper level than the destination.
Personally, I would use the second sentence to avoid redundancy. Adding "en bas" to the verb "descendre" is useful to clarify the context. If you have already a "complément circonstanciel de lieu" (de la colline) you don't need it to add "en bas".
"En bas", and equivalently "en haut", adds some reachability nuance.
In "Je descends en bas de la colline", it feels like it's going to take some time, because it's pretty far away.
In this sense, some people will laugh at you if you say "Je monte en haut" to mean "I'm coming upstairs", because "upstairs" is so reachable, precising it is useless.
However, if it's something unusual, "en haut" could be added without sounding odd, provided a context follows:
Je suis monté en haut de la Tour Eiffel.
Je suis descendu en bas de mon immeuble.
In the same way, adding "tout", to make "tout en haut" / "tout en bas" will remove any odd feeling, because it emphasis the fact that the destination is far away.
Je suis monté tout en haut des escaliers. (Very contextual, but can be heard)
Contrarily, using "monter" without "en haut", or "descendre" without "en bas" as well, makes feel that the destination is close. Typically, "monter sur" or "descendre de" are used for a chair, a horse...
Je suis monté sur la table.
Je suis descendu du cheval.
About your question:
Il est déjà descendu de la colline ?
feels a bit weird, unless the hill is small. I think a better phrasing would be:
Il est déjà redescendu de la colline ?
because "redescendre" sounds like "to come back (down)", which is more appropriate for something like a hill.