If you read the paper carefully, it makes very interesting reading. For example, the identification of the La Brana remains as having Y haplotype C6 specifically is not completely certain. To quote:
"The mean coverage obtained for the Y chromosome (1.4x) prevented us from recovering phylogenetically relevant SNPs at high coverage. However, using unfiltered data, we were able to narrow down the paternal lineage affiliation of La Braña 1 individual (Table S9). The presence of the derived allele in many different mutations defining haplogroups A1, A1b, BT, CT and CF suggests La Braña 1 sample belongs to either haplogroup C or F. When mutations defining those haplogroups were checked, only ancestral alleles were found in the haplogroup F-defining mutations, whereas seven C-defining mutations (M130, M216, P255, P260, V183, V199 and V232) showed only derived alleles. Thus, La Braña 1 most likely belonged to haplogroup C. The actual distribution of haplogroup C is thought to be a consequence of a single out of Africa migration through Southern Asia, followed by a northward migration that eventually reached Siberia and the Americas. The fact that we found ancestral alleles in mutations defining C1, C2, C3 and C4 (Table S9), together with their actual phylogeographic distribution restricted to Asia, Oceania and the Americas suggests that our individual does not belong to any of these branches. Rather, a new branch within haplogroup C (C6, originally named C7) has recently been identified in several men from Southern Europe, suggesting this could be an ancient European clade. Importantly, mutation V20 showed one read with the derived allele (A), which points to C6 as the most probable sub-clade for La Braña 1 sample. It could also be possible that this G to A mutation is a result of DNA damage. Other less likely haplogroup affiliations are C* and C5 (no read covered SNP M356), both found mainly in present- day India. Besides the V20 mutation, four other positions could have potentially been assigned wrongly due to the presence of DNA damage. However, their allele state is phylogenetically coherent with the rest of the SNPs studied. The precise affiliation of La Braña 1 in the Y-chromosome phylogeny could be better determined in the future with more data and increased genomic coverage."
It also seems that the idea that the La Brana person had dark skin and blue eyes is a probability rather than a certainty.
"Furthermore, using the alleles present in La Braña 1 for the six most informative SNPs for eye color prediction69 and for other SNPs associated to hair color, the HIrisPlex model was applied (Table S22). We obtained a probability of 0.780 and 0.202 for having black and brown hair respectively. Regarding the eye color prediction, no data could be recovered for SNP rs12896399. Thus, accounting for the three possible genotypes in this SNP, we obtained a probability range of 0.706-0.458, 0.214-0.117 and 0.328-0.177 for blue, intermediate and brown color respectively. If it can be confirmed that La Braña 1 had blue eyes with the genotyping of the SNP rs12896399, it would be so far the oldest known individual carrying this trait. The combination of seven SNPs has also been shown to be useful in the prediction of “not-dark” and “not white” skin color in a global human sample. However, some of these SNPs are not variable between Asians and Europeans and thus, its usefulness for skin color prediction in an ancient, European-specific genetic background is debatable. Moreover, the model, developed for forensics purposes, is based on the number of these SNPs present in a particular individual. La Braña 1 has the non-dark allele in rs6119471 (two copies), rs12913832 (two copies) and rs12203592 (one copy). As a conclusion, it is very difficult to ascertain the precise skin pigmentation phenotype of La Braña 1 individual from the comparison with modern human populations because the two critical pigmentation SNPs (at SLC45A2 and SLC24A5 genes) are essentially fixed in extant Europeans. Although some neighbouring populations such as Middle Easterns or North Africans can carry these ancestral alleles, their general genetic background is still quite different from that of modern Europeans and especially from Northern Europeans, to which La Braña 1 displays clear affinities. It is likely that La Braña 1 represents a unique phenotype that is no longer present in modern Europeans."
Of course, these "maybe" statements are to some extent just typical of scientists, who will mention even the slightest doubts about their results. But they didn't seem to have any doubts about the relationship between the La Brana man and Mal'ta Boy.
"Table S10 presents result for this analysis, indicating that the Mal’ta individual is closer to the La Braña 1 individual than it is to any European population, with the exception of Orcadian and Russian populations. We also calculated D statistics using all the East Asian population from the HGDP, and found that the Mal’ta individual is significantly closer to the La Braña 1 individual than it is to the East Asians (Table S11). "
So Mal'ta Boy, despite being R*, is related to someone who's C, and possibly C6. Okay, maybe not related, but genetically closer to than most modern European populations.