As a class feature, a paladin's mount does not have a challenge rating, since it's already factored into the Paladin's challenge rating The same applies to animal companions and familiars. While it is never explicitly stated, defaulting to the person whose class feature they are does make sense in circumstances like these.
As such, Paladin's CR +5 seems like the logical conclusion but this is a situation that doesn't seem to be covered by the rules, despite that it should probably have been. By a very strict reading of the rules, they would probably gain a spell resistance of 5, which at level 11 is useless.
Either way, it's obviated just a few levels later (as you pointed out) and barring an official ruling or erratum somewhere, Paladin's CR +5 seems the closest to the rules option we have available.
Animal companions with an intelligence < 3 have a rather small list of feats to choose from, as stated here. Given the fact that your T-Rex is strength based, then the feats that come to mind are Power Attack and Improved Natural Attack.
At level 7, Power Attack would let your T-Rex take a -2 penalty on attack rolls to gain a +6 bonus on damage rolls. (I would rule a +8, because of Powerful Bite, but since this is PFS, it's best to settle for Rules As Written.)
This penalty can be turned on or off, so if you find you're having a particularly hard time scoring a hit, you can turn off Power Attack to deal normal damage without the attack penalty.
It is important to note that the bonuses from power attack scale as you level up, but they shouldn't change until you reach level 13.
At level 7, improved natural attack would permanently bump up your T-Rex's bite damage dice to a staggering 3d6. This is a passive ability that has no drawbacks, so if you have to pick just one feat, I would recommend Improved Natural Attack over Power Attack. (Unless you've been eyeing bull rush or overrun combat maneuvers, because Power Attack is needed to qualify for those feats.)
You can read the particulars about these feats here:
Power Attack
Improved Natural Attack
Edit:
Sorry, I didn't see that your T-Rex's Intelligence is 3, I dug a bit and it seemed that most of the good feats required way more than 3 feats to build for, but I found a few that could also work for your T-Rex:
Blood Feast, A +1 attack and damage after your first hit with your bite attack.
Cleave, You can gobble up 2 foes at once by taking a -2 to AC. Requires Power Attack.
Great Cleave, Only useful for mowing down the mooks, you can use cleave on as many enemies you can reach. Requires Cleave and Power attack.
Furious Focus, You no longer take the penalties from Power Attack on the first attack you make every turn! Requires Power Attack.
Improved Sunder, You can chew up your foes weapons and armor, leaving them squishy and vulnerable. Requires Power Attack.
I would recommend Furious Focus, unless you want to avoid Power Attack, then the only other damage feat I could find was Blood Feast. It is important to note that your T-Rex can't take Vital Strike until level 9.
Best Answer
A typical starting character just doesn't have the resources to meet this demand well for any meaningful length of time. The magical and monetary resources just aren't available yet. (For example, while both muleback cords cost 1,000 gp and a heavyload belt costs 2,000 gp—the least expensive options—can be worn by a typical biped animal companion, those magic item slots are unavailable to a Society PC's player-bound creature without a feat.) As a starting character, the choice—if your vision is so fixed—is, really, either get a bigger mount or play a littler character. (Also note that a Pathfinder human can weigh as little as 95 lbs. if female and 130 lbs. if male, so you can eke out a precious few more pounds by being short and skinny.)
…But you can just ride Rexy anyway
An animal companion tyrannosaurus only sees its speed reduced to 20 ft. if it's at medium encumbrance, and, while it suffers a −2 penalty to Armor Class if at heavy encumbrance, it still has a speed in combat of 20 ft. while bearing such a load. In other words, as long as you keep things light—keeping you and your gear under 178 lbs.—you can ride your more-than-lightly-encumbered T-rex into battle anyway… it'll just look even funnier when you do, as it strains under the comparatively massive bulk.
Further, for those times when the creature must move at full speed, on the hunter spell list is the spell longstrider that increases the mount's speed (due to the supernatural ability share spells) for 1 hour by +10 ft. Scrolls of the spell are a mere 25 gp (and subject to Society availability, of course).