Considering the output of a cryptographic primitive, like an encryption scheme (CBC, ...), a hash function or even the output of any schemes based on number theoretic assumptions, is it reasonable (acceptable) to assume that these outputs are random when proving the security of a protocol/algorithm which relies on the use of such a primitive? Is this a good starting point?
The answer is "it depends". There are two fairly commonly used sets of assumptions, the so-called standard model, and the random oracle model. In the standard model, hash functions are one-way functions. In the random oracle model they are random oracles. The random oracle model isn't actually true, but it is useful and many protocols inspired by it are in fact secure as no one has been known to attack them.
For ciphers the usual model is PRP, pseudo-random permutation, although the ideal cipher model is also used, but generally PRP is realistic and strong enough to prove things secure.
Number theoretic primitives do not output random strings. For instance DH never produces all zeros. You should use hashing to make this truer.
For protocols usually a game is designed where an adversary tries to get bad things to happen. Showing that the game is lost if the cipher is a PRP implies that a real version will be secure if the cipher behaves like a PRP, and so is generally considered a proof of security. However, the constants involved matter: if you haven't read DJB "Non-uniform cracks in the concrete" you should before embarking on any sort of provable security work.
The answer I normally see is the protocol's documentation will reference the strength of the underlying algorithm. You don't have to assume it's perfect, just adequate.