The tests assume Paren is defined in a specific way. This works:

data Paren :: Nat -> Nat -> * where
    PEmpty :: Paren Z Z
    PLeft :: Paren a (S b) -> Paren (S a) b
    PRight :: Paren a b -> Paren a (S b)

but this does not:

data Paren :: Nat -> Nat -> * where
    PEmpty :: Paren Z Z
    PLeft :: Paren a (S b) -> Paren a b
    PRight :: Paren a b -> Paren (S a) (S b)

The latter will cause this error message:

test/Kata/TestSpec.hs:101:38: error:
    • Couldn't match type ‘'S 'Z’ with ‘'Z’
      Expected type: Paren s ('S a2)
        Actual type: Paren ('S 'Z) ('S 'Z)
    • In the expression: PRight PEmpty
      In the expression: [PRight PEmpty]
      In an equation for ‘appendRights’:
          appendRights PEmpty = [PRight PEmpty]
    |
101 |               appendRights PEmpty = [PRight PEmpty]
    |                                      ^^^^^^^^^^^^^

But there is nothing that says only the former should be correct (since both are isomorphic); and from the usage we only care about the Paren n Z cases.

Use `shouldBe` instead of == for random tests. You ( well, solvers :) get useful failure messages for free.

There could be a makeParen function that given n :: Int, generates all possible sequences of valid parentheses

-- in Kata.PairedBracket
makeParen :: Int -> [Paren]

-- in Test Cases
show <$> makeParen 0 == []
show <$> makeParen 1 == ["()"]
show <$> makeParen 3 == ["((()))", "(())()", "()(())", "()()()", "(()())"]