Yes, Northrend at 68 depending on gear is a breeze. I had some early BC stuff when I went there and it was a little challenging for a couple of quests, but nothing insane.
There is a blue quality axe you can get in Borean soon after arriving.
Horde - http://www.wowhead.com/?quest=11916
Alliance - http://www.wowhead.com/?quest=12019
Which gives you...
http://www.wowhead.com/?item=38237
Quote:
Axe of Frozen Death
Binds when picked up
Two-Hand Axe
341 - 513 Damage Speed 3.60
(118.6 damage per second)
+37 Strength
+54 Stamina
Durability 100 / 100
Equip: Improves hit rating by 28 (1.98% @ L68).
Equip: Improves critical strike rating by 43 (2.17% @ L68).
The alliance quest is rather short but requires a 3 person group quest that's very difficult to solo, even for a ret paladin (although I'm sure some BC raid geared paladins did).
The Horde version requires multiple chains out of Warsong Hold, but all of them are soloable.