Under certain conditions, yes
The Rescue Maneuver
The rescue maneuver begins on the pegasus's turn and requires the following:
- The paladin is falling normally, and has not yet hit the ground.
- The pegasus has sufficient flying speed to reach a point 500 feet directly above the paladin before the end of its turn without using its action.
The pegasus begins its turn by taking any movement required to position itself 500 feet directly above the paladin. Then it drops prone.
You can drop prone without using any of your speed. Standing up takes more effort; doing so costs an amount of movement equal to half your speed. (Player's Handbook, pages 190-191, section "Being Prone")
The DM rules that the pegasus is permitted to drop prone while flying.
If a flying creature is knocked prone, has its speed reduced to 0, or is otherwise deprived of the ability to move, the creature falls, unless it has the ability to hover or it is being held aloft by magic, such as by the fly spell. (Player's Handbook, page 191, section "Flying Movement")
The DM rules that a flying creature that chooses to drop prone falls, subject to the rule above. The pegasus cannot hover and is flying by wing power, so it falls.
When you fall from a great height, you instantly descend up to 500 feet. If you're still falling on your next turn, you descend up to 500 feet at the end of that turn. This process continues until the fall ends, either because you hit the ground or the fall is otherwise halted. (Xanathar's Guide to Everything, page 77, section "Rate of Falling")
If you use the rule for rate of falling in the previous section, a flying creature descends on the turn when it falls, just as other creatures do. (Xanathar's Guide to Everything, page 77, section "Flying Creatures and Falling")
The DM agrees that the pegasus falls 500 feet, ending its movement adjacent to the paladin.
But if that creature starts any of its later turns still falling and is prone, it can halt the fall on its turn by spending half its flying speed to counter the prone condition (as if it were standing up in midair). (Xanathar's Guide to Everything, page 77, section "Flying Creatures and Falling")
The DM agrees that the pegasus can end its fall by using its movement to recover from prone.
[...] you can take the Ready action on your turn so that you can act later in the round using your reaction.
First, you decide what perceivable circumstance will trigger your reaction. Then, you choose the action you will take in response to that trigger, or you choose to move up to your speed in response to it.
The pegasus takes the Ready action, with the following trigger and response: "When the paladin mounts me, I will use my movement to recover from prone." The DM agrees that this readied action is permitted. The pegasus then ends its turn.
Some time later, the paladin's turn begins. Since the paladin is falling, they will descend 500 feet at the end of their turn. Before that happens, the paladin mounts the pegasus.
Once during your move, you can mount a creature that is within 5 feet of you or dismount. Doing so costs an amount of movement equal to half your speed. (Player's Handbook, page 198, section "Mounting and Dismounting")
The DM agrees that the paladin retains their speed even when they are falling, and can use half of it to mount the pegasus. The pegasus's readied action then triggers, and the pegasus recovers from prone and is no longer falling. The paladin is now mounted on a flying creature, so it is also no longer falling.
(Note the points in the above scenario where the DM agrees to a ruling not explicitly stated in the rules. I consider these to be reasonable rulings, but if your DM disagrees, then this maneuver won't work.)
Getting In Position
If the paladin is knocked off their mount during or after their own turn, but before the pegasus's turn, they fall 500 feet immediately. As long as they are more than 500 feet above the ground, and haven't been knocked more than 90 feet horizontally, they are in position for the rescue maneuver, and can be rescued as above.
But what if the paladin is unhorsed after the pegasus's turn, but before the paladin's turn? The paladin falls 500 feet immediately, and then at the end of their first turn after the dismounting event, they fall an additional 500 feet. The pegasus begins its first turn 1000 feet above the paladin, and is unable to reach the rescue maneuver position on its turn.
Instead, the pegasus can attempt to catch up to the paladin. On its first turn it can dash 180 feet straight down, then drop prone and fall an additional 500 feet, reducing the distance to 320 feet. On its second and third turns it can recover from prone using half its flying speed, then dash to descend an additional 135 feet and drop prone again. By the beginning of the pegasus's fourth turn, the paladin has descended 2500 feet (500 feet for the initial fall, plus four turns of falling 500 feet each), and the pegasus is 550 feet above the paladin and is thus in position to perform the rescue maneuver.
Conclusion
Accepting all of the above, the pegasus may be able to rescue the paladin if they were flying more than 500 feet above the ground, and definitely can if they were flying more than 2500 feet above the ground.