You need to remove the %{ and %} from around the part of the PROMPT that prints the working directory.
PROMPT='%(?..%F{red}%?%f:)%F{blue}%n%f:%F{green}${PWD/#$HOME/~} %(!.%F{red}.%f)%# %f'
The %{ and %} sequences are meant to be placed around bits of the prompt that do not affect the position of the cursor (e.g. a hard-coded control sequence). By surround something that actually moves the cursor (by printing your current working directory), you are confusing zsh’s notion of where the cursor is; when it needs to redraw part of the current line (e.g. when you use C-r to search), it ends up putting the cursor in the wrong location.
You can verify this by changing to a directory with a longer printed representation: if you cd /tmp, then the cursor will be out of place by 4 columns (the length of /tmp) instead of 1 (the length of ~).
Also, you can usually use %~ instead of ${PWD/#$HOME/~} to include the current working directory. Accordingly, if that was your only substitution, you could then turn off PROMPT_SUBSTPROMPT_SUBST.
Also, with ${PWD/#$HOME/~}, you'd have problem if $PWD contains % or control characters. It's best not to have uncontrolled data in the contents of $PROMPT if possible, and if that can't be avoided, you'd want to do some escaping so that it still makes sense as a prompt string.
