Cameo works great for people who aren't so dull that every celebrity they're interested in is a super-wealthy A-lister.
I paid Spike and Drusilla, from Buffy, to say/sing happy birthday to my wife. Neither are top-tier actors, but they're both completely recognizable James Marsters in particular I guess, as he's done a lot of narration for things like the Dresden Files.
There were "super-popular" actors available, for significant sums, but these two were cheap enough that it was a no-brainer to gamble on a good result, and both were fantastic.
Have no fear: basically anyone with a lot of IG followers will work with you on a low friction sponsorship.