How to test Semigroup law for this data type?

You can't decide whether two functions are equal. But you can test it!

Two functions are equal if and only if for any input they give the same output. This is a testable property: generate some inputs, compare the outputs. If they are different, you've got a counter-example.

-- Test.QuickCheck.(===) requires (Eq b, Show b)
-- but you can use (==) if you prefer.
funEquality :: (Arbitrary a, Show a, Eq b, Show b) => Combine a b -> Combine a b -> Property
funEquality (Combine f) (Combine g) =
  property $ \a -> f a === g a

Notice that the Bool result in the type of "decidable equality" (==) :: X -> X -> Bool is replaced with Property in what we might call "testable equality" funEquality :: X -> X -> Property. It's actually not necessary to use property and convert the function a -> Property (or a -> Bool if you use (==)) to Property, but the types look neater that way.

We need to rewrite the function corresponding to the associativity property, since we no longer rely on Eq.

type CombineAssoc a b = Combine a b -> Combine a b -> Combine a b -> Property

combineAssoc :: (Arbitrary a, Show a, Eq b, Show b, Semigroup b) => CombineAssoc a b
combineAssoc f g h = ((f <> g) <> h) `funEquality` (f <> (g <> h))

Edit: at this point we're actually still missing a Show instance for Combine. QuickCheck provides a wrapper Fun to both generate and show functions as counterexamples.

main = quickCheck $ \(Fn f) (Fn g) (Fn h) ->
  (combineAssoc :: CombineAssoc Int Bool) (Combine f) (Combine g) (Combine h)

Indeed it is not possible or at least not feasible, however you don't really need a test case with such a big argument type as Int!

For smaller types, e.g. Int16, you can just exhaustively try all possible arguments to determine equality. The universe package has a convenient class for that:

import Data.Universe

instance (Universe a, Eq b) => Eq (Combine a b) where
  Combine f == Combine g = all (\x -> f x == g x) universe

Then your original check will work, albeit unacceptably slow; I'd recommend changing it to quickCheck (semigroupAssoc :: CombineAssoc Int16 Bool).