Yes, you can take higher-level Stances at your first class level

There are several issues here.

First of all, this line is in the form of a descriptive statement, not a prescriptive one: it describes the usual case of things, rather than defining a limitation on your options. I would argue that it is there solely to help players new to the book, who are creating their first martial adept from level 1.

After all, a great many statements are made in Wizards’ products that assume you are single-classed, and starting from ECL 1 is the default assumption for the game. The Wizard’s Specialization feature says you cannot cast spells from your banned schools – but you actually can, you just need to get that ability from another class.

In addition, the line does not say “first-level martial adepts are restricted to 1st-level Stances.” It says that they “begin play” with a single 1st-level maneuver. A multiclass character taking his first level in a martial adept class after ECL 1 is not “begin[ning] play,” so the statement does not apply to him.

For that matter, taken literally, that would imply that any martial adept has only a single 1st-level Stance when the game starts – even if he started at level 20 and took Martial Stance feats repeatedly. Clearly, this is not the case, which is only further evidence that the line is not a rule, but a hint or (supposedly) helpful description.

Finally, if you rule that it does prevent higher-level Stances from being taken for your first class level, it flies in the face of the entire Tome of Battle design pattern. Tome of Battle was intentionally designed to mesh well with previous books and existing characters – that is why the Initiator Level rules were written the way they were in the first place.

Every single other method of learning any maneuvers – Stances included – allows those with higher Initiator Level to “skip” lower-level maneuvers – because Wizards finally understood how important it was to the system that characters be getting level appropriate class features, even if they multiclass. For instance, a 12th-level character, with no martial adept levels, still has an Initiator Level of 6, and can take Martial Study or Martial Stance to get a 3rd-level maneuver or stance, respectively.

This single supposed exception does not make any sense in light of the context that Tome of Battle provides, does not have the form of a prescriptive rule, and does not actually specify your first martial adept level but rather whether or not the character is “beginning play,” which really does not make much sense if taken literally.

The Beloved of Valarian, as you have noticed, isn’t really intended for Paladins. You can get in (and wind up with both a unicorn and another mount, which could itself be a unicorn), but you don’t progress any of those abilities, which means stagnating your Smite, your spells, and that mount that you’re interested in.

Really, the class is for Rangers to become quasi-paladins, because you can just

Be a Paladin, have a Unicorn, worship Valarian, call yourself Beloved

The primary class feature of the Beloved of Valarian class is the unicorn companion. Well, a Paladin can just have one of those.

In the Dungeon Master’s Guide, page 204:

A paladin of 6th level or higher can use a [...] unicorn [...] as a mount.

So instead of getting a not-unicorn special mount at 5th level, get a unicorn at 6th level. You count as one level lower than your actual paladin level for the purposes of your special mount’s features.

Then worship Valarian, and you’ll effectively be one of the Beloved. A reasonable DM should have no problems with you calling yourself one/being treated like one in-character, either.

This is actually better than what a Beloved of Valarian gets, because your Special Mount improves with level, while the Beloved’s does not aside from the Telepathic Bond and Celestial Charger class features. Paladins instead receive an Empathic Link, though, and the Celestial template doesn’t do much to an already-intelligent unicorn. Despite not having the Celestial template, the unicorn is “from the celestial realms.”

Otherwise, you’re lacking a couple of +2’s to wilderness-y skills; you can easily get these from feats if you desire them. Timelessness, Uncanny Dodge, Nature’s Understanding, and Wood Repulsion aren’t very high-impact features, though the Timelessness is a nice one from a flavor perspective. One solution would be to be a race that gets Timelessness anyway; another could be to just ask the DM for it since it’s not really going to change the game, just change your character’s outlook on life.

The hard ones are ethereal jaunt and mass baleful polymorph. They’re both just once per day, but they’re also both reasonably powerful and fairly flavorful. These you would simply have to accept you aren’t going to get without actually taking the Beloved of Valarian class.

Unless your DM agrees to work with you:

Were I your DM, I’d work with you to build a feat chain for high-level Paladins of Valarian to get these features. Maybe something like these:

Beloved

Requirement: Must be a paladin of Valarian with a unicorn as a Special Mount

Benefit: You gain the Timelessness quality, add Knowledge (nature) and Survival and paladin class skills, and add the following spells to your paladin spell list:

1st: calm animals, charm animal, delay poison, detect snares and pits, entangle, eyes of the avoral, longstrider, pass without trace, speak with animals

Special: If you turn away from the faith of Valarian, you lose this feat and any feats that require it. You regain this feat if you return to the faith (including any atonement that may be necessary).

Because you can’t get the unicorn mount until 6th level, you can’t take this feat any earlier than that, either.

Entrusted

Requirement: Beloved

Benefit: You may, once per day, become ethereal as if by the ethereal jaunt spell cast by a sorcerer of your paladin level.

You also add the following spells to your paladin spell list:

2nd: barkskin, hold animal

3rd: heart’s ease, neutralize poison, remove disease, water walk

Since it requires Beloved, you don’t get this until level 9, the same level as a Beloved of Valarian. Also, you don’t need special rules about sharing the spell with your mount, because you have the Share Spells feature.

Spear of Valarian

Requirements: Entrusted, ability to cast 4th-level Paladin Spells

Benefit: Once per day, you may cast a special version of the baleful polymorph spell that affects all evil creatures within 30 feet of you (as a 10th-level druid). Affected creatures are transformed into harmless Diminutive mammals (rabbits, squirrels, or the like) or Fine vermin (nonthreatening spiders, centipedes, or the like). All affected creatures are transformed into the same type of creature. See the baleful polymorph spell description in the Player’s Handbook for details.

You also add the following spells to your paladin spell list:

4th: blinding beauty, commune with nature, freedom of movement, spear of Valarian

The requirement of 4th-level Paladin Spells puts this to 15th level; a bit earlier than when a Beloved of Valarian gets it, but reasonable enough.

These allow you to be a paladin, while earning some of the special features that Beloveds get in a timely fashion, without making them “freebies.”