StringMap.hs

{-# LANGUAGE RankNTypes, TypeFamilies, ConstraintKinds #-}
import Data.String
import Data.String.ToString
import Text.XML.HXT.Arrow.Pickle
import GHC.Exts

import qualified Data.Map.Strict as SM

f :: (C map key, C map String, XmlPickler (map String value), IsString key, ToString key)
        => (forall k k'. C map k => (k -> k') -> map k value -> map k' value)
        -> PU (map key value)
f mapKeys = xpWrap (mapKeys fromString, mapKeys toString) xpickle

type family C (m :: * -> * -> *) :: * -> Constraint
type instance C SM.Map = Ord

instance (Ord a, IsString a, ToString a, XmlPickler b) => XmlPickler (SM.Map a b) where
  xpickle = f SM.mapKeys

You also need a C map k' constraint on the higher-order function. In fact, I think you only need it on k', not k.