Wireframes são traços que não se preocupam com a estética, mas sim com a completeza do entendimento. Não servem para demonstrar como o software ficará em termos visuais, mas ajudam muito no entendimento do que o software deve fazer. É mais barato e mais rápido de ser produzido do que um mockup. Mockups são bons para coletar feedback, inclusive sobre aspectos visuais (embora não se preocupem tanto com uma aderência visual ao produto final que deverá ser entregue como o fazem os protótipos "clássicos"). São mais custosos e mais demorados de serem produzidos do que um Wireframe. Cada um deve ser aplicado de acordo com a necessidade da elicitação e análise dos requisitos.
É bom lembrar que tanto Mockup quanto Wireframe, nesse contexto citado no parágrafo anterior, pertencem ao gênero Protótipos. No entanto, não é difícil encontrar descrições que apontam o termo Protótipo como uma espécie do mesmo nível de Mockup e Wireframe. Sendo que Protótipo seria mais custoso, mais demorado, com maior comprometimento com o que seria, tanto em termos visuais quanto em termos de funcionalidades, o produto final a ser entregue. Nesse contexto, de protótipo como uma espécie, ele seria mais custoso que um Mockup. Assim, do mais custoso e mais demorado de ser produzido, porém com resultados adicionais em termos de eficácia, para o menos custoso e mais rápido, teríamos, nessa ordem: Protótipos, Mockups e Wireframes.
Sobre o desenho em papel, sim. Conceitualmente, é uma técnica milenar de prototipagem.
:) Bons treinos!