Text search by first order formula
The formula's you propose are very reminiscent of the operations of monadic second order logic: position variables, existence letter on position, relative order of positions, boolean operators and position quantification. As you probably know the power of this scheme equals regular languages.

The transformation from MSO to FSA seems to be horrible (negation is complementation, and existential quantification is handled using nondeterminism, hence exponential blow-up for each combination of the two).   

Nevertheless, that gives a very different complexity, linear in $n$, but multiplied by a tower of 2-powers of height $k$.