There is the LeftRightSpatialCalculator that might warrant a look.
Otherwise the NeighborFinder is a good contender, you could use e.g. look at the difference between _closest_base_x and _closest_candidate_x to determine the east-west direction (negative or positive result), and the _closest_base_y and _closest_candidate_y for the north-south direction.
To account for orientation, you could split up any polylines into single line segments (Chopper, vertex=2) and then use the HorizontalAngleCalculator to find the azimuth of each segment.
I don't have time to dive into this right now (though I'd love to) but...
There's a custom transformer called the HorizontalAngleCalculator, which calculates the angle of a line. Then the NeighborFinder (putting in the lines as base features and the points as candidates) can calculate the angle from the base to the candidate. The difference between those two angles should give you an indication of left/right.
@david_r and @redgeographics I think i have a solution. Using only LeftRightSpatialCalculator gave me mix of results because it calculated side for every line in data set. But then I had an idea to use NeighborFinder to attach unique ID of lines to points that are closest to them, then in LeftRightSpatialCalculator i Group by that ID and at first glance I think I have right results. I am attaching my workspace and test data set so anyone can inspect it. leftright.fmw Test_Data.zip