Why does paging not have external fragmentation?
The details depend on the processor architecture, but the principle is the same everywhere. All page tables of a given type at a given level have the same size. When all memory blocks have the same size, there is no fragmentation: a memory block is allocated starts at an offset which is a multiple of the block size, so the size of any hole is a multiple of the block size. If a gap opens in the page table, the operating system can use this gap the next time it needs to allocate a page table.

Furthermore the size of a page table pretty much always divides the size of a page — both are powers of two. So a page contains a whole number of page tables with no leftover space. This means that the operating system can allocate pages for page tables and no table spreads over multiple pages, so there's no need for the page tables to be consecutive and therefore there's no fragmentation of the address space for the page tables themselves.