All you need to get started are 2 Shielded Minibots and 2 Muster for Battles. Don't worry about the other legendaries/epics for now, for any deck really since they'll come slowly after you get good at Arena. When I first built paladin, I put in Frostwolf Warlord and Imp Master as substitutes for stuff xD
Do you have Naxx? Sludge and Zombie chow alongside decent creatures for each slot should be powerful enough to sustain a basic Paladin deck. It's defensive but still proactive, and can be a blast as it's strong vs aggro and control alike. It also offers a challenge of skill without being too complex, and is good training for Arena playstyle.