que codigo mas raro.. pa que vuelves a poner <? si ya estas con codigo php? ademas, hazlo asi por lo pronto:
Código PHP:
$rs=mysql_query("Select * from Paises Order by pai_nombre", $conexion);
//$Datos= mysql_fetch_array ($rs); //esto lo quitas que por esto te pilla a partir del 2º
while($Datos=mysql_fetch_array($rs))
{
echo "<option value='".$Datos['pai_id']."'>".$Datos['pai_nombre']."</option>";
}
por lo demas yo no veo nada.. prueba eso que te puse a ver..