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>