É bem fácil, mas não direto.
Instale o AbiWord. Abra o PDF e copie todo o texto para o Abiword. Salvar como e escolha o formato PalmDoc. Este é realmente o formato MobiPocket e pode ser lido pelo MobiPocket Reader no meu BlackBerry. Não testou no Kindle, não possui um, mas deve funcionar.
Como alternativa, você pode usar o pdftoabw (do pacote poppler-utils no Ubuntu e no Debian) para converter o PDF diretamente no formato AbiWord, o que pode preservar a formatação / imagens melhor do que copiar e colar.