Consider stamping wherever possible - that is, for each position and rotation of the stamp, if stamping here would only paint on black grid cells, stamp here. If there is a sequence of stampings $S$ that produces the grid, then stamping wherever would also produce the grid because it would contain each individual stamping in $S$ and it will never "overstamp". Therefore, it suffices to check at each of $(N-K+1)^2$ positions and under each of $4$ rotations whether the $K\times K$ region has paint in every cell the stamp has paint.

To try each position, we can use a nested for loop - one over x and one over y. To account for rotations, we can nest another loop that runs $4$ times - after each iteration, we rotate our stamp. We can rotate our stamp array by setting $stamp[i][j]$ to $stamp[j][K-1-i]$ (0-indexed). See code for implementation details.

Ben's code:

T = int(input())
for _ in range(T):
    input()
    N = int(input())
    grid = [list(input()) for _ in range(N)]
    K = int(input())
    stamp = [input() for _ in range(K)]
    ans = [['.' for _ in range(N)] for _ in range(N)]
    for rot in range(4):
        for i in range(N-K+1):
            for j in range(N-K+1):
                if all(grid[i+a][j+b] == '*' or stamp[a][b] == '.' for a in range(K) for b in range(K)):
                    for a in range(K):
                        for b in range(K):
                            if stamp[a][b] == '*':
                                ans[i+a][j+b] = '*'
        stamp = [[stamp[j][K-1-i] for j in range(K)] for i in range(K)]
    print("YES" if grid == ans else "NO")