Pure bash, ~738

Encoder first (something golfed):

#!/bin/bash
# Ascii 85 encoder bash script
LANG=C

printf -v n \\%o {32..126};printf -v n "$n";printf -v m %-20sE abtnvfr;p=\<~;l()
{ q=$(($1<<24|$2<<16|$3<<8|$4));q="${n:1+(q/64#378iN)%85:1}${n:1+(q/614125)%85:1
}${n:1+(q/7225)%85:1}${n:1+(q/85)%85:1}${n:1+q%85:1}";};k() { ((${#p}>74))&&ech\
o "${p:0:75}" && p=${p:75};};while IFS= read -rd '' -n 1 q;do [ "$q" ]&&{ print\
f -v q "%q" "$q";case ${#q} in 1|2)q=${n%$q*};o+=($((${#q}+32)));;7)q=${q#*\'\\}
o+=($((8#${q%\'})));;5)q=${q#*\'\\};q=${m%${q%\'}*};o+=($((${#q}+07)));;esac;}||
o+=(0);((${#o[@]}>3))&&{ [ "${o[*]}" = "0 0 0 0" ]&& q=z|| l ${o[@]};p+="${q}";k
o=(); };done;[ "$o" ]&&{ f=0;for((;${#o[@]}<4;)){ o+=(0);((f++));};((f==0))&&[ \
"${o[*]}" = "0 0 0 0" ]&&q=z||l ${o[@]};p+="${q:0:5-f}";};p+="~>";k;[ "$p" ]&&e\
cho "$p"

Tests:

for word in easy test code\ golf Programming\ Puzzles ;do
    printf "    %-24s %s\n" "$word:" $(./enc85.sh < <(printf "$word"))
  done
    easy:                   <~ARTY*~>
    test:                   <~FCfN8~>
    code golf:              <~@rGmh+D5V/Ac~>
    Programming Puzzles:    <~:i^JeEa`g%Bl7Q+:j%)1Ch7Y~>

and decoder now:

#!/bin/bash
# Ascii 85 decoder bash script
LANG=C

printf -v n "\%o" {33..117};printf -v n "$n";o=1 k=1;j(){ read -r q||o=;[ "$q" \
]&&[ -z "${q//*<~*}" ]&&((k))&&k= q="${q#*<~}";m+="$q";m="${m%~>*}";};l(){ r=;f\
or((i=0;i<${#1};i++)){ s="${1:i:1}";case "$s" in "*"|\\|\?)s=\\${s};;esac;s="${\
n%${s}*}";((r+=${#s}*(85**(4-i))));};printf -v p "\%03o" $((r>>24)) $((r>>16&255
)) $((r>>8&255)) $((r&255));};for((;(o+${#m})>0;)){ [ "$m" ] || j;while [ "${m:0
:1}" = "z" ];do m=${m:1};printf "\0\0\0\0";done;if [ ${#m} -ge 5 ];then q="${m:0
:5}";m=${m:5};l "$q";printf "$p";elif ((o));then j;elif [ "${m##z*}" ];then pri\
ntf -v t %$((5-${#m}))s;l "$m${t// /u}";printf "${p:0:16-4*${#t}}";m=;fi;}

Copy this in enc85.sh and dec85.sh, chmod +x {enc,dec}85.sh, then:

for string in '<~ARTY*~>' '<~FCfN8~>' '<~@rGmh+D5V/Ac~>' \
            '<~:i^JeEa`g%Bl7Q+:j%)1Ch7Y~>' ;do
     printf "    %-42s %s\n" "$string:" "$(./dec85.sh <<<"$string")"
  done
    <~ARTY*~>:                                 easy
    <~FCfN8~>:                                 test
    <~@rGmh+D5V/Ac~>:                          code golf
    <~:i^JeEa`g%Bl7Q+:j%)1Ch7Y~>:              Programming Puzzles


./enc85.sh <<<'Hello world!'
<~87cURD]j7BEbo80$3~>
./dec85.sh <<<'<~87cURD]j7BEbo80$3~>'
Hello world!

But you could do some stronger test:

ls -ltr --color $HOME/* | gzip | ./enc85.sh | ./dec85.sh | gunzip

Reduced to 724 chars:

printf -v n \\%o {32..126};printf -v n "$n";printf -v m %-20sE abtnvfr;p=\<~
l(){ q=$(($1<<24|$2<<16|$3<<8|$4))
q="${n:1+(q/64#378iN)%85:1}${n:1+(q/614125)%85:1}${n:1+(q/7225)%85:1}${n:1+(q/85)%85:1}${n:1+q%85:1}"
};k() { ((${#p}>74))&&echo "${p:0:75}" && p=${p:75};};while IFS= read -rd '' -n 1 q;do [ "$q" ]&&{
printf -v q "%q" "$q";case ${#q} in 1|2)q=${n%$q*};o+=($((${#q}+32)));;7)q=${q#*\'\\}
o+=($((8#${q%\'})));;5)q=${q#*\'\\};q=${m%${q%\'}*};o+=($((${#q}+07)));;esac;}||o+=(0)
((${#o[@]}>3))&&{ [ "${o[*]}" = "0 0 0 0" ]&&q=z||l ${o[@]};p+="${q}";k
o=();};done;[ "$o" ]&&{ f=0;for((;${#o[@]}<4;)){ o+=(0);((f++));}
((f==0))&&[ "${o[*]}" = "0 0 0 0" ]&&q=z||l ${o[@]};p+="${q:0:5-f}";};p+="~>";k;[ "$p" ]&&echo "$p"