Long story short, I’ve taken probably a week or two now searching up side scrolling games but more specifically one that has puzzles. I started looking into what makes a ‘good’ side scrolling / puzzle game but I haven’t came across much and it would be pretty nice to know and learn some more information especially from people who have already worked with this type of genre or has played many of them.
Fun puzzle element that is fun to do and keeps offering new challenges.
How do you quantify “fun” though? Well, that is the intuition / talent part 
A good game designer/developer of course!
Joke aside, I think a simple control yet interesting mechanic will make it more fun. Example, Ski Safari, Whale Trail.
I wouldn’t say Ski Safari is a puzzle game at all, but I can agree about it being fun/simple. 
Have a look at games like VVVVVVVV (not sure how many V’s in the title officially). There are also lots of others. To make it a puzzle game you have to introduce problems, which typically are mental challenges where things don’t initially make sense and therefore you have to figure it out in order to get your mind to where you can see the solution. It could be that you organize objects in a particular order that isn’t right initially and you have to do something to put them in order, or there’s some sequence that has to be gone through to open up a door, or certain tasks that you have to perform in a particular combination to move forward, etc, or objects that you have to interact with in a certain way in order to trigger something. Also a lot has to do with level design, because when you want puzzles in a side-scroller it’s mostly to do with the environment itself presenting you with problems. In VVVVVVVV for example the interesting dynamic is you can flip gravity to play in the environment right-side-up or upside-down, which creates different paths through the room, but you also have to be careful with timing and jumping/falling to avoid dangerous spikes, etc… so figuring out how to navigate through the puzzle of the level design is the main part of the gameplay, then using this special skill or talent (such as inverting gravity) is the tool that you must use/master in order to achieve it. So probably you need a cool/interesting control system coupled with some interesting puzzle dynamic.
I’m making a puzzle platformer at the moment and most of the puzzle comes from level layout, combined with a limited range of motion of the player, which means you can’t just move through the level without thinking, you have to figure out how to perform several moves in order to get to where you want. Also certain obstacles in the level layout introduce extra problems to solve that have to be factored into your strategy. Think also of a game like Portal - it’s 3D, okay, but basically you have a level that’s laid out in a particular way and the way to proceed through it isn’t obvious because you have a handicap (can’t access everywhere on-foot) and a special ability (the portal gun), so you have to figure out how to use what you’ve got to overcome the appearance of a problem. So I’d say that you need to place some kind of limitation on the player’s abilities, even if it’s just that they can only run-and-jump and not fall too far, and then assemble a level that has to be solved by working within those limitations. And if you can make it so that the player has some kind of special ability (like the gravity flip), that’s simple and easy to use, then you can further design the level layout to require that you use that ability at the right time and place to overcome the structural challenges. Without limitations on the player you won’t be able to get the player into a position where they’re thinking well I can't go that way, or do that, because I'll die, but maybe I can do this....
So to make a good/fun sidescrolling puzzler you need clever level design, a player handicap/limitation, a special unique ability/dynamic that is fun and interesting and ideally one which bends the rules like going against normal physics or having a superpower or something, … then it’s a matter of good level design and timing and progression of thought/teaching tactics over time etc … and making the visuals fun and memorable.
Take a look at Trine
Trine is similar to Max and the Magic Marker. … draw physics shapes etc to overcome problems… different kind of approach to puzzles. Somewhat more action game than typical platform puzzler?
Thanks for the reply everyone!
imaginaryhuman I really appreciate you taking the time to write up all of that and you gave me a ton to think about and I’m starting to pull together a few things here and there. Very helpful, thank you 
For a more literal side-scrolling AND puzzle game amalgamation take a look at Henry Hatsworth in the Puzzling Adventure on the Nintendo DS (http://www.youtube.com/watch?v=kpjE12swfJE); this literally bolts the two genres together for really interesting and fun results - maybe not exactly what you are asking for but a unique take on the genre(s) for sure 