We consider mixtures of self-avoiding multiarm star polymers with hard colloids that are smaller than the star polymer size. By employing computer simulations, and by extending previous theoretical approaches, developed for the opposite limit of small star polymers [A. Jusufi et al., J. Phys.: Condens. Matter 13, 6177 (2001)], we coarse-grain the mixture by deriving an effective cross-interaction between the unlike species. The excellent agreement between theory and simulation for all size ratios examined demonstrates that the theoretical approaches developed for the colloidal limit can be successfully modified to maintain their validity also for the present case of the protein limit, in contrast to the situation for mixtures of colloids and linear polymers. We further analyze, on the basis of the derived interactions, the non-additivity parameter of the mixture as a function of size ratio and star functionality and delineate the regions in which we expect mixing as opposed to demixing behavior. Our results are relevant for the study of star-colloid nanocomposites and pave the way for further investigations of the structure and thermodynamics of the same.