Si jalas los paises de la BD, solo guardalos en un array y los muestras con HTML. Por ejemplo:
<?php
foreach($paises as $id => $pais) {
//array(4) {[1]=>"México", [2]=>"Colombia", [3]=>"Bolivia", [4]=>"España"}
?>
<input type="checkbox" name="pais[]" value="<?=$id;?>"><label><?= $pais; ?></label></input>
<?php } ?>
El "foreach" aquí lo que hace es iterar cada elemento del array y desplegar un checkbox con la información correspondiente al elemento. El resultado final quedaría algo así:
<input type="checkbox" name="pais[]" id="1"/><label>México4</label>
<input type="checkbox" name="pais[]" id="2"/><label>Colombia</label>
<input type="checkbox" name="pais[]" id="3"/><label>Bolivia</label>
<input type="checkbox" name="pais[]" id="4"/><label>España</label>