How can I walk this type with a recursion scheme instead of explicit recursion?

I found a solution that I'm reasonably happy with: an apomorphism.

makeReplacements replacements = apo coalg
  where
    coalg :: MyStructure -> MyStructureF (Either MyStructure MyStructure)
    coalg structure = case lookup structure replacements of
      Just replacement -> Left <$> project replacement
      Nothing -> Right <$> project structure

Having thought about this a little more, I also saw a symmetry in this that leads to an equivalent paramorphism:

makeReplacements replacements = para alg
  where
    alg :: MyStructureF (MyStructure, MyStructure) -> MyStructure
    alg structure = case lookup (embed $ fst <$> structure) replacements of
      Just replacement -> replacement
      Nothing -> embed $ snd <$> structure

Following up from the discussion under your question

para is (Base t (t, a) -> a) -> t -> a. To me, this looks close but not quite perfect. Wouldn't I actually want ((t, Base t a) -> a) -> t -> a or ((t, Base t (t, a)) -> a) -> t -> a so that I can look at the element I'm on?

That's still a paramorphism. The type of para looks weird but it is the more precise one. A pair (t, Base t a) does not encode the invariant that both components are always going to have the "same" constructor.

What you propose still seems like the most natural way of defining makeReplacements, it's just not defined in the recursion-schemes library.

para' :: Recursive t => (t -> Base t a -> a) -> t -> a
para' alg = go where
  go x = alg x (fmap go (project x))