Need help understanding convolution indexing
This question is plagued by bad notation that the OP is unwilling to abandon because, unfortunately, his book uses it. This greatly
impedes his understanding of the concepts.


  Case 1: First convolution equation example:
  $$
h[k] * h^*[-k] = \sum_{n=-\infty}^{\infty} h[n] \ h^*[n+k]
$$
  
  The way I got the right hand side, was:
  
  1) Make the $h$'s have dummy variables, so $h[n]$ and $h^*[-n]$. 
  
  2) Flip one of them around, so now I get $h[n]$ and $h^*[n]$
  
  3) Add the delay $k$ into the one that way flipped, so finally I have $\sum_{n=-\infty}^{\infty} h[n] \ h^*[n+k]$.


${}{}{}{}{}$

No. 3) is not correct. When convolving, you flip one signal and then move it to
the right by $k$ which will give you $h^*[n-k]$, not $h^*[n+k]$.  Thus you end
up with $\sum_n h[n]h^*[n-k]$ as in the leftmost sum in $(2)$ below.


  Great, I have a convolution.  (emphasis added)


The right side of the last equation is not generally called
a convolution; it is called the autocorrelation function of $h$.
If $h$ and $g$ are two finite-energy sequences (meaning $\sum_n |g[n]|^2$
and
$\sum_n |h[n]|^2$ are finite), then the $k$-th term of
their convolution is
$$\sum_{n=-\infty}^\infty h[n]g[k-n] = \sum_{n=-\infty}^\infty h[k-n]g[n].
\tag{1}$$
It is not a good idea to use $h[k]\star g[k]$ to denote the
convolution in general or its $k$-th term in particular
-- far better to write
$h\star g$ in general and $(h\star g)[k]$ in particular -- as the
OP has already been told repeatedly on math.SE. Be that as it may,


  for the case when $g[n] = h^*[-n]$ for all $n$, we can write $(1)$ as
  $$\sum_{n=-\infty}^\infty h[n]h^*[n-k] = \sum_{n=-\infty}^\infty h[k-n]h^*[-n]
= \sum_{m=-\infty}^\infty h[m+k]h^*[m]
\tag{2}$$
  where the last equality was obtained by replacing $n$ by $-m$.
  Notice the difference from the OP's result. For complex-valued
  sequences, there are two different ways of defining the autocorrelation
  function $R_{hh}[\cdot]$ depending on which sequence we choose
  to conjugate, but both ways give the same conjugate symmetry
  property $R_{hh}[-n] = (R_{hh}[n])^*$.


${}{}{}$


  Case3: The problem:
  
  This is my problem. Case 1 showed the steps for how to do a normal convolution. (emphasis added)
  Case 2 showed how the method of substitution works. However, if I try to solve Case 1 using this substitution method, I get the wrong answer, even though it worked on case 2. Why is that?
  
  To wit - where am I going wrong here?


Where you are going wrong is that your analysis
of Case 1 is not quite correct
as explained above, while your Case 2 is not a convolution at all,
and is not an autocorrelation or cross-correlation of complex-valued
sequences either, because these require conjugation of one of the
terms.  So you are really mixing up things and then complaining that
the answers are not the same.