Localized magnetic moments randomly scattered on the surface of a two-dimensional conductor with quasi-relativistic electronic spectrum are shown to exhibit a high-temperature susceptibility strongly deviating from the Curie-Weiss law. This effect is caused by the non-integrable short-distance singularity of the electron-mediated RKKY exchange between the localized spins resulting in the failure of the standard mean-field theory. A modification of the mean field theory resolving this problem is proposed and then applied to the experimentally interesting systems such as magnetic atoms on graphene and on the surfaces of topological insulators.