Besides direct molecular interactions, proteins and nanoparticles embedded in or adsorbed to membranes experience indirect interactions that are mediated by the membranes. Membrane-mediated interactions between curvature-inducing proteins or nanoparticles can lead to assemblies of particles that generate highly curved spherical or tubular membrane shapes, but have mainly been quantified for planar or weakly curved membranes. In this article, we systematically investigate the membrane-mediated interactions of arc-shaped particles adsorbed to a variety of tubular and spherical membrane shapes with coarse-grained modelling and simulations. These arc-shaped particles induce membrane curvature by binding to the membrane with their inner, concave side akin to N-BAR domain proteins. We determine both the pairwise interaction free energy, which includes entropic contributions due to rotational entropy loss at close particle distances, and the pairwise interaction energy without entropic components from particle distributions observed in the simulations. For membrane shapes with small curvature, the membrane-mediated interaction free energies of particle pairs exceed the thermal energy