How can I make parts of a menu context sensitive in Python?
Answering my own question via vitos1k on IRC.

In order for the the if/elif statements to recognize the variable it needs to be placed inside the draw function. 

Correct code:

class QuickObjectOptions(bpy.types.Menu):
bl_idname = "object.display_options"
bl_label = "Quick Object Options"

def draw(self, context):

    mode = context.object.mode
    layout = self.layout

    if mode == 'OBJECT':
        layout.operator("object.shade_smooth", icon='SOLID')
        layout.operator("object.shade_flat", icon='MESH_UVSPHERE')
    elif mode == 'EDIT':
        layout.operator("mesh.faces_shade_smooth", icon='SOLID')
        layout.operator("mesh.faces_shade_flat", icon='MESH_UVSPHERE')