There's no point in using a static pattern rule here, since the pattern doesn't appear in the prerequisites list. However, I assume you also wanted to include the .c file as a prerequisite here.
Why do you include the Pattern in the pattern match?
You can just write:
CFLAGS = -I ../headers -Wall
EXECUTABLES = testPattern testPatterns
$(EXECUTABLES): % : %.c pattern.o
g++ $(CFLAGS) $^ -o $@
ETA
It appears a better example that would show the real issues you face would be something like this:
EXECUTABLES = someThing somePattern morePatterns
where you want a static pattern rule that matches the two binaries containing Pattern but not the others.
As I said in my comment below, you cannot do this with a single pattern which means you can't do it in the target part of a static pattern rule.
However, you could do it like this:
$(foreach E,$(EXECUTABLES),$(if $(findstring Pattern,$E),$E)): % : %.c pattern.o
g++ $(CFLAGS) $^ -o $@
This basically loops through each entry in EXECUTABLES and tests to see if it contains the string Pattern, and if so expands to that string else expands to nothing.