First of all, I should clarify that what you write $Hom(C_*,D_{*+n})$ is, more precisely $\prod_m Hom(C_m,D_{m+n})$. I think it needs clarifying, because the $Hom$ you wrote could be taken to mean hom in the category of chain complexes.
Second of all, to me, this notion of internal hom is justified by the tensor product : $Hom(C,-)$ is right adjoint to $-\otimes C$, where $\otimes$ is the usual tensor product of chain complexes, and this entirely determines $Hom$ in an essentially unique way. It's a fun exercise to actually derive the definition of $Hom$ from that of the tensor product, using that they are adjoint (in the above sense)
(you already noted that the two are connected, but in my mind, it's the tensor product that comes first - or at least that's how I understand those things)
Before going on and explaining why the tensor product is what it is let me note that this Hom also enjoys some good properties (which, admittedly, would not help you define it if you were stuck on a desert island) : its $H_0$ is precisely $Hom(C,D)$ modulo homotopy, and more generally in fact you can find interpretations for its $H_i$'s in terms of chain maps of shifts $C[n]$ modulo homotopy.
You need to find the right sign conventions for that, but they can be fun to figure out (those ones you could find on a desert island !)
Ok now the tensor product, where does it come from ? Well I hope first of all that the fact that, as graded groups, $(C\otimes D)_n = \bigoplus_{p+q=n}C_p\otimes D_q$ is clear, and if I understand correctly, your problem is with the sign conventions.
For tensor products of chain complexes, there are two sign conventions : one for the differential, and one for the symmetry isomorphism $C\otimes D \cong D\otimes C$. They may look different, but in fact they are both instances of the same convention : the Koszul sign convention.
I remember hearing somewhere that it had a precise definition and all, but I don't know that definition, so I'll give the vague understanding that I have (and that a lot of people seem to have) :
Whenever you're in a graded setting, and have two symbols $x,y$ that you can put next to one another, either as $xy$ or $yx$, then switching from one to the other should introduce a sign which is $(-1)^{|x||y|}$, where $|a|$ denotes the degree of $a$
I'll try to explain this sign convention a bit later, but let's take it for granted for now, and let's see how it provides the definition for the differential on $C\otimes D$.
First of all, note that we want to define the differential on each $C_p\otimes D_q$, and since it's linear, we want to define it on each $c\otimes d, c\in C_p,d\in D_q$.
So we're faced with $\partial (c\otimes d)$. Now you can argue out of functoriality (if you want more detail I can add some, but it's quite fun to work out) that this must be a linear combination of $(\partial c) \otimes d$ and $c\otimes (\partial d)$. Now you can see that in the first term, no symbols have been exchanged, so there should be no sign in front of it. In the second term, however, you've had to move the $\partial$ past the $c$.
$\partial$ has degree $-1$ (which is just $1$ mod $2$) and $c$ has degree $|c|$, so you should add a sign which is $(-1)^{-|c|} = (-1)^{|c|}$ in front of that second term.
Now you get the pretty good looking formula $\partial (c\otimes d) = (\partial c)\otimes d + (-1)^{|c|} c\otimes (\partial d)$. I haven't justified why the coefficients should be $1$ but I think it's a pretty reasonable guess to make.
I think you can prove that you don't have a choice about those coefficients if you want associativity in a reasonable way (that is, compatible with associativity on the underlying graded abelian groups)
For symmetry, you want to go from $c\otimes d$ to $d\otimes c$, well you're moving a $c$ past a $d$, so you get a $(-1)^{|c||d|}$ terme in front, which gives you this good-looking symmetry-isomorphism : $C\otimes D\to D\otimes C$, $c\otimes d\mapsto (-1)^{|c||d|} d\otimes c$
So the Koszul sign convention explains those signs. In fact, it can actually (vaguely) explain them for the hom complex as well ! Indeed, suppose you have a family $f_m :C_m\to D_{n+m}, m\in\mathbb Z$. Then you want to compute $\partial(f(c))$ for some $c$. Well once again, you have to first "associate" to get $(\partial f)(c)$ (no exchange of symbols here) and then move the $\partial$ past the $f$ to get to $f(\partial c)$, with a $(-1)^n$-sign : it's $n$ because $f$ has degree $n$ and $\partial$ has degree $-1$.
This gives you $\partial \circ f = \partial f + (-1)^{|f|} f\circ \partial$, in other words : $\partial f = \partial \circ f - (-1)^{|f|} f\circ \partial$. Note that this is different from yours, but since I followed the Koszul sign rule, I know mine is the correct sign convention.
And indeed, in degree $0$, $\partial f = 0$ if and only if $\partial\circ f - f\circ \partial = 0$, i.e. $\partial f = 0$ if and only if $f$ is a chain map (which gives the interpretation of $H_0$ I mentioned earlier).
Ok so the Koszul sign rule seems to explain pretty much all the "weird" signing conventions, but how do we explain the Koszul sign rule ? Where does it come from ?
I don't know how this was done historically, so don't take what I'm saying for a historical account, but I think mainly the inspiration comes from differential forms and the $\wedge$-product. Indeed if you are in, say, euclidean space, you have stuff like $\mathrm dx_1 \wedge \mathrm dx_2 = - \mathrm dx_2 \wedge \mathrm dx_1$ etc.
Differential forms are the basic example of graded things we encounter "naturally", and they "automatically" come with this sign rule. Indeed, we tend to think of objects in degree $p$ as "compositions of objects in degree $1$", and so moving something in degree $p$ past something in degree $q$ requires $pq$ exchanges, and each exchange introduces a minus sign, so you end up with a $(-1)^{pq}$-sign.
Another place where this sign rule comes up without it being a convention is in basic topology. If you look at $\mathbb R^{n+m} \to \mathbb R^{m+n}$, the linear map which moves the $n$ first coordinates past the $m$ last coordinates, this has determinant $(-1)^{nm}$. This may not seem like much, but if you compactify this self-homeomorphism you get a self-homeomorphism $S^{n+m}\to S^{m+n}$, which corresponds to a point in $\pi_{n+m}(S^{n+m})\cong \mathbb Z$, and with the identification that identifies $id_{S^{n+m}}$ with $1$, this self-map is identified with $(-1)^{nm}$. So in spheres, moving things in degree $n$ past things in degree $m$ induces a sign $(-1)^{nm}$, and this is not a convention, this is absolute.
Since chain complexes and topology are intimately related, it's not surprising that the same kind of thing pops up in both places; and in fact the Koszul sign rule allows everything to be consistent between algebra and topology (that is : we could define algebraic gadgets without the Koszul sign rule, but then it simply wouldn't be compatible with topology, precisely because of the thing I mentioned)
Hopefully this has clarified at least some amount of things. If some of it is still unclear, don't hesitate to ask, or to go have a look at Tyler Lawson's notes, which take sign conventions back from the beginning - they might actually also help you go further.
Best Answer
One algebraic way to motivate this is to observe that the signs in the differential for the Hom are precisely what is needed for 0-cycles in the $\hom(A,B)$ complex to be the set of morphisms of complexes $A\to B$ (and also, that the 0th homology group $H_0(\hom(A,B))$ is the set of homotopy classes of morphisms $A\to B$). This is quite great.
Once you decide you want this, all the other signs you mention follow because you need various things to hold. For example, you want the adjuntion between $\hom$ and $\otimes$ to hold for the internal versions, so this forces you to add signs to the $\otimes$, and so on.
A topological, indirect explanation for the appearence of most signs is that in the long exact sequence of bases maps corresponding to a map $f:X\to Y$, which looks like $$X\to Y\to C(f)\to S(X) \to S(Y) \to S(C(f)) \to \cdots$$ there is a "sign" which you cannot get rid of. This sign reproduces itself in every algebraic version.