When you set a border on a block this way, what it does is it creates a new div element around the block and gives that new div element a border.

So what you are doing is not going to change the border of your button.

Now the reason you don't see a border appear is that you set its color but you left its width at 0. You need to give it some width.

But to achieve what you want, you have to either modify your theme's CSS file directly.

Or alternatively, you could get one of the plugins from the marketplace that allow you to build and style your buttons. there are 2:
http://www.concrete5.org/marketplace/addons/cta-buttons...
http://www.concrete5.org/marketplace/addons/buttons-pro...

Full disclosure, the second one is mine. It has way more options and possibilities (popup, popover, dropdown...) and really full control over the design of your buttons but if you don't need all the bells and whistle maybe try the other one.