Paging divides linear address-space into 4K pages.
Generating a linear address from a logical seg:off works the same (adding the segment_base of the selected segment to the offset) regardless of whether the linear address will be used directly as a physical address (paging disabled) or treated as virtual and translated by the page tables (paging enabled).
The term "linear address" exists because of segmentation, not paging, and dates back to 8086. (Paging was new for x86 in 386).
The whole point of enabling paging is changing the meaning of some kind of address from physical to virtual, and in x86 those addresses happen to have another name that still applies even with paging enabled. In other ISAs like ARM without segmentation, you'd just say "addresses change meaning from physical to virtual when paging is enabled". In x86 we're also just adding an extra step at the end of address-generation; what would be physical addresses without paging are now virtual.
Segmentation base+offset is done before paging as you say. Note that segment bases are 32-bit in 32-bit protected mode; the selector itself is 14 bits (plus the bottom 2 bits being ring0-3 privilege level), but changing the GDT/LDT and reloading a segment with a selector is possible. Or of course you could just use large segments to cover more of 32-bit linear address-space.
Mainstream OSes don't really use segmentation except for thread-local storage via a non-zero FS or GS base; they set all other segments to base=0 / limit=unlimited, so linear=offset and all 32-bit pointers are linear virtual addresses. So functions that accept pointers can just take a simple 32-bit pointer with no segment selector, and work on pointers to stack memory (normally accessed via SS), static storage and memory-mapped files (normally via DS or ES), or machine code (normally via CS).
(64-bit mode of x86-64 makes this flat memory model the only option, only allowing non-zero FS and GS bases for TLS.)
