If a journal publishing an article about a software tool requires the software to be freely available, must the article be open access? I am interesting in publishing a Bioinformatics software as a paid access article in a journal where they have open access as well as paid access options (Oxford's Bioinformatics). 

But it stated at the journal's website that


  Software If the manuscript describes new software tools or the implementation of novel algorithms the software must be freely available to non-commercial users at the time of submission, and appropriate test data should be made available. Availability must be clearly stated in the article. Authors must also ensure that the software and test data is available for a full TWO YEARS following publication. The editors of Bioinformatics encourage authors to make their source code available and, if possible, to provide access through an open source license (see www.opensource.org for examples). Authors should make every effort to use URLs that will remain stable. At the minimum, authors must provide one of: webserver, source code or binary. The name of the software should be included in the title of the paper wherever possible. 


Does that mean the article publishing that software must be an open access article?  or can it be a paid access article?
The two are entirely independent.

The journal does not require you to make the software open source. It merely requires you to make it free for non-commercial use for at least two full years from the day of submission of the article.
It however recommends that you make the source available, preferably via an open source license. But it states that it is even acceptable to simply provide the compiled binary to the editors. (Presumably to verify that the software does what you report it to do.)

The requirement is only applied to a software if you wish to publish a paper describing a new software tool or a new implementation or algorithm. (Which seems to be your case as you want to write about a new bioinformatics software.)

The OA publishing option is something else entirely. The default publishing format in the journal is subscriber pays. With payment of additional fees you can purchase the option to make your paper open access, but that is not a requirement.

I note that the condition described in point 1 would be evaluated at the time of submission by the editorial board, whereas the possibility of publishing the article open access will not generally be discussed at all until after the paper is accepted.