Microsoft Visio 2013 how to resize an object and maintain its aspect ratio?

Looks like there is a protection feature set that includes an Aspect Ratio option. You'll need to run in Developer mode and then you'll get some extra options. Check out the Office support article with instructions here:

https://support.office.com/en-au/article/Prevent-or-allow-changes-to-shapes-e65decf4-0eed-4fd6-a7d9-b286abcbc7eb

Use the Shift key like you tried, but use the handles on one of the sides instead of a corner. I'm not sure why ratio is kept via side handles but not corners, but that's how it's working for me.