Marcar para remoção remove o pacote, mas não os arquivos de configuração associados ao pacote. É equivalente a
apt-get remove package_name
Marcar para Remoção Completa limpa o pacote, ou seja, remove os arquivos do pacote e sua configuração. É equivalente a
apt-get --purge remove package_name
Do manual do Gerenciador de Pacotes Synaptic:
3.2. To Remove Packages
Configuration files and user created data (e.g. a website in "/var/www") are not removed from the system by default.
Debian only: You can change the default behavior in the preferences.
Debian only: To remove all files related to the package choose Mark for Complete Removal instead of Mark for Removal.