How to generate a (valid) PDF with "a2ps foo.txt"?
The a2ps utility is for formatting files for printing on a PostScript printer, hence its name is not a2pdf.

The file you created under Linux (or OS X), which is a miss-named .pdf file, is in fact a PostScript file and many Linux Distros will open it anyway.  Thus leading you to believe is was a PDF Document when in reality it's not.

Looking at the file created under Linux in a Hex Editor its header starts off with, e.g., %!PS-Adobe-3.0 and a PDF Document starts with, e.g., %PDF-1.6%.

This is why you get the "The file “filename.pdf” could not be opened. It may be damaged or use a file format that Preview doesn’t recognize." error message under OS X when trying to open a PostScript Document with a miss-named PDF Document extension.

Update: Installing a2pdf

After doing a little research I found a2pdf.  Further research required having Font::TTF::Font and PDF::API2 also installed.  So I downloaded all three packages master.zip (for a2pdf), Font-TTF-1.04.tar.gz and PDF-API2-2.023.tar.gz.

Next I extracted all three and installed them in the same manner in the following order, Font::TTF::Font, PDF::API2 then the master.zip (for a2pdf).  I did this in a Terminal using the following commands.

$ cd $target_directory
$ perl Makefile.PL
$ make
$ sudo make install


I then tested, from my Home Directory, with: a2pdf filename.txt &gt; filename.pdf

It create filename.pdf and I then opened it in Preview just fine as a PDF Document.

That said, there are other modules that can be installed to do things like syntax highlighting, e.g. Perl::Tidy.  So you'll need to do a bit more research to utilize the full capabilities of a2pdf.

Note: I have Xcode and Command Line Tools for Xcode installed and as long as you have Command Line Tools for Xcode installed, which is a Homebrew prerequisite, you can install all of this from the Terminal the old fashioned way if not available from Homebrew, which I do not believe it is.