I think if a magic weapon pops up early you have to take it regardless of its ability since Valeros will get stonewalled by magic enemies. Of course later you can switch it out but an early magic weapon is vital against Valeros' only combat weakness. Even keeping one in deck to keep in hand or even two to give one away at beginning to Lini is useful.
As for first skill point into strength I think is an overkill. Maybe in later adventure decks the additional strength will be useful but a base 1d10+3 plus 2 die from a weapon plus blessing die if desperate will pretty much take care of any combat encounter you face. IMO the first point should be to Charisma to help him acquire more allies so he can explore more locations followed by the second point in dex to help him with barrier checks as well as helps his attacks with the one or two ranged weapons you have in your deck.
Power feat to hand size 5 is a no brainer as 4 card hand is very limiting in your options.
Card feat it totally depends on your party makeup and card pool. But should be a decision between blessing, ally, item. A 1-3 party group with a good item pool selecting item feat is a good idea since most of the time you're worrying about losing to damage instead of the blessing timer so multiple exploration is not as important. in 3-6 player groups I say blessing since it gives much more flexibility compared to allies. Unless you're running with a heavy blessing group with Sajan, Kyra, and Seoni in it then going Ally would probably be best.