trovare è tuo amico. Credo che quanto segue dovrebbe farlo:
find <target_dir> -not -name \*.bz2 -exec bzip2 \{\} \;
cioè se la directory in cui si trovano i file che vuoi bzip è /var/log/blah sarebbe:
find /var/log/blah -not -name \*.bz2 -exec bzip2 \{\} \;