The first one will not work. It's identical to johngg's solution, except missing the non-greedy quantifier after the first parenthesis. Thus it will only find the last match rather than all of them (and it will return it twice).
Your second regex works, and is probably the semantically cleanest solution posted so far. It also shouldn't be that slow, especially if the ratio of "fred" occurrences to the total length of the string is low. It can be generalized to arbitrary $n like this (note that the "!= 0" is redundant):
/fred(?(?{ (pos()-4) % $n })(?!))($capture)/g
However, if this regex is reused for multiple values of $n which is declared with my in the parent scope, it seems to keep using the first one (like a closure). Declaring the $n with our seems to fix this.